Re: Re: maximum finite domain constraint for eclipse

On Sun, Feb 04, 2001 at 06:36:28PM +0000, Joachim Schimpf wrote:
> Rui wrote:
> > On a special note to the list. I don't know what is the policy about posts
> > and so I am not sure if this kind of post fits in.
> 
> Seems to be just the thing to discuss here :-)

Good.

> 
> 
> > Btw, Any comments about my implementation? Is it efficient?
> > Can it be improved?
> 
> It is in fact surprisingly tricky to get these things right.
> Even this apparently straightforward max-constraint shows many
> of the problems that can come up, but that makes it a perfect
> example to study!
> 
> 
> First, your code can be simplified by removing all the special
> handling of non-variables. This is possible because most of the
> primitives that work on domain variables also work on integers
> (considering them as variables with identical upper and lower
> bound). This leaves essentially the last clause of your code.
> The only place where you still have to check for variables is
> where you decide whether to re-suspend or not:

I knew that most primitive worked on integers as well. My implementation
suffered from the curse of continuous editing. The reason I had sepparated
the cases was to simplify the reading (heh) and possible modifications in
the special cases.

[Code snipped]
> 
> Another important change I have made was to swap the order of
> suspend(...) and M::Min..Max.

This one baffles me. I had the naive impression from one of the examples on
the manual that the other constraints were only ``activated'' when wake was
called.

> This can be important for correctness when the constraint is
> used in a constraint-network together with other constraints
> that have higher priority. The line M::Min..Max affects the
> domain of M. This may wake other constraints, and if these have
> higher priority, they are executed immediately (before M::Min..Max
> returns). These other constraints may directly or indirectly
> affect the domain of A and B again, which in turn requires maxfd/3
> to be executed again. But that can only work if we have already
> suspended it before!

Read you loud and clear.

> 
> 
> The next point is that you don't do all the propagation that is
> possible! It is natural to think of the max-constraint as computing
> the maximum of two numbers, but in fact a constraint is a relation.
> Therefore the "output" argument M can also affect the "input"
> arguments A and B. For example

You are again right, I didn't look at the constraint as a relation, I guess
I was biased by M #= max(A, B). My mistake.

[Snip]
> 
> An interesting general point is that we have now split the single
> max-constraint into 3 "propagators" which share the job of implementing
> the constraint's semantics. This is a typical choice that one has to
> make when implementing a constraint:
> 
> - either one propagator that does everything
> - or many specialised propagators
> 
> There is no general rule about what is more efficient. It depends on
> the particularities of the constraints and also on the actual pattern
> of domain updates at runtime.  For example, when only lower bound
> updates to A happen at runtime, then cheap, specialised propagators
> will be more efficient because the irrelevant ones never wake up. 
> If updates happen randomly to all 6 bounds, then a single propagator
> might be more efficient because there is less waking and re-suspending
> going on.

I guess that in some cases it is hard to know which one would be more
appropriate. As usual, a generic implementation is not always the best way
to solve all the problems and in some special cases, implementing a specific
one for the problem at hand might be the best.

> 
> I have now used the lower-level primitives dvar_remove_smaller
> and dvar_remove_greater instead of ::/2 and #=</2.
> This is somewhat more efficient, but otherwise equivalent.

Yup, as I guess that ::/2 and #=</2 may call those lower-level primitives
themselves.

> 
> Also, I have wrapped all the updates of M, A and B together with
> the re-suspend code into a call_priority/2. This makes the whole
> sequence sufficiently "atomic", i.e. any waking of other constraints
> will be postponed until the end of the call_priority. This is an
> alternative way to achieve what we did before by playing with the
> order of modification and re-suspension.

Interesting, took a note of that as well.

[Snip again]
> 
> After all this, is it worth remembering that the most "complete"
> implementation of a constraint is not necessarily the best under all
> circumstances.  In our example, the perfect constraint has to wake up
> on all 6 possible changes (upper/lower bound change on 3 variables). 
> Every change may or may not represent a propagation opportunity.  If
> it doesn't, we have just wasted time, and we would possibly have been
> better off using a cheaper, incomplete implementation.  By the way,
> this is one reason why most so-called "benchmarks" of constraint
> systems are quite useless.

That is one aspect I already had in mind. That the most "complete"
implementation of a constraint is not necessarily the best. Well, that is
one reason why constraints like A*B #= 10 do not prune all the spurious
values from A and B and leave only the ones that can possibly work.

> 
> 
> There are more interesting aspects, but I leave then for later...
> Just want to mention that the library(fd_global) contains a
> generalisation of the max-constraint called maxlist/2, which computes
> the maximum of a list, but also works efficiently for 2 variables.

Well, thank you Joachim for taking your time to explain some of the
important notions behind propagation and Eclipse. I learned a few things
with your modifications of my code.

>  Joachim Schimpf              /             phone: +44 20 7594 8187
>  IC-Parc, Imperial College   /            mailto:J.Schimpf@ic.ac.uk
>  London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse
> 

--Rui Mendes