Re: [eclipse-clp-users] Assignment propagation queue

Lars Kotthoff wrote:
> Dear all,
> 
>  I was wondering whether Eclipse (specifically search/6 from the ic library)
> does any dynamic reordering of the propagation queue. Does it process events in
> the order they're fired or does it use a heuristic like most constrained
> variable first?

I suppose you want to use this information in some kind of comparison between
your own work and ECLiPSe, so we better try to be precise here ;-)

1. I assume with "events" you mean things like variable instantiation,
change of variable bounds, removal of value from domain.  These events
exist in ECLiPSe, some are defined in the kernel (instantiation, variable
aliasing), some are defined by solver libraries (e.g. bounds change in ic),
more can be added by the programmer.

2. ECLiPSe does not queue events, it queues propagators.  Propagators
are attached to events, i.e. they get triggered by events (see suspend/3,4).

3. Propagators have priorities attached (1-12).  When a trigger event
occurs, all the propagators attached to the event get scheduled
according to their priority, i.e. they get inserted into a priority queue.
Currently, once a propagator is scheduled for execution, it keeps its
priority level in the queue (this could be changed to allow "bumping up"
an already scheduled propagator's priority, but is not currently done).

4. The queue of scheduled propagators is processed from higher to lower
priorities. There is no guaranteed processing order within one priority
level.

5. When an event occurs during propagator execution, and this event triggers
higher-priority propagators, then these of course get inserted into the
queue ahead of the currently executing one.  The propagator implementor
can chose whether they want to be interrupted by these higher priority
ones (ie. allow nesting of propagators), or whether they should get queued
until the currently running one is finished.

6. A propagator's priority CAN be changed at runtime.  Some ic propagators
do that as a heuristic: they reduce their own priority in case they got
triggered, but did not achieve any propagation, so that next time they
get triggered, they will be scheduled with a lower priority.


To come back to your question:
 >  I was wondering whether Eclipse (specifically search/6 from the ic library)

search/6 has nothing to do with it.  It only makes branching decisions.
These decisions (instantiation or domain change) will of course trigger
propagation, but this is completely orthogonal.

 > does any dynamic reordering of the propagation queue.

I hope this has been answered above.

 > Does it process events in the order they're fired

It's a 2-stage process: events are "processed" immediately, but they
mainly schedule propagators, which are then executed priority-based.

 > or does it use a heuristic like most constrained variable first?

You would have to explain more precisely what you mean by that in the
context of a propagator-queuing implementation.  Propagators typically
involve many variables.  You could write a propagator that increases
its own priority when it involves highly constrained variables.


Cheers,
Joachim