Re: An specific question about propagation.

Hi Oscar,

The two constraints of interest are (as you say):

(1)	ST1 + SDur #>= AT1 + ADur

and

(2)	AT1 + SDur #>= AT1 + ADur

Logically, they are equivalent, since you also have the constraint:

(3)	ST1 #= AT1

However, there is a difference in the way ECLiPSe handles them at compile
time.  For the second constraint, ECLiPSe notices that there are two
occurrences of the same variable in a linear constraint, and groups them
together as part of FD's constraint pre-processing.  In this case they
actually cancel each other out, resulting in the simplified constraint:

	SDur #>= ADur

Still, you might wonder why this is a better constraint than (1) given (3).
The answer is that ECLiPSe's FD solver does not do any global reasoning on
constraints: each constraint is considered independently from all the
others.  So while looking at (1), it does not know that ST1 and AT1 should
be the same, and so treats the two terms independently.  To see this,
consider how (1) is used to update SDur.  Basically, we have:

	SDur >= AT1 + ADur - ST1

Thus the lower bound of SDur is known to be at least as great as the sum of
the lower bounds of the terms AT1, ADur and (-ST1).  These are 0, 10, and
-10000000 (the negation of the upper bound of ST1), respectively, so the
bound deduced is actually -9999990, much worse than the current bound of 0.

I hope this illustrates sufficiently well what is happening, and why it is
good to avoid having what is essentially the same variable or expression
appearing more than once in a constraint (particularly if they appear with
opposite sign or should otherwise cancel out).  It should also clearly
illustrate that the propagation algorithms used in such finite domain
solvers are inherently incomplete: to ensure you have a solution, you must
in general assign a value to every variable, since some elements of the
domains of the variables may not be part of any valid solution.


There are constraint solvers out there that detect multiple occurrences of
variables which are related to each other in some simple way (such as the
equality relationship you have here) and act appropriately; indeed, this was
part of my PhD work at Melbourne Uni, and if you are particularly interested
I can send you a couple of papers about it.  However, such features have not
been implemented in ECLiPSe at this stage.  They may be added to the IC
solver at some point, but no particular time frame has been set for this
(there are many more important things which should be done first).

Note also that in most cases, the problem is not as bad in practice as it
might at first appear: either such constraints do not occur, the domains are
much smaller, or the search phase quickly narrows the domains to something
quite reasonable.  Of course there are exceptions: for one of the problems I
studied for my thesis, the difference in execution time was orders of
magnitude.

Cheers,
Warwick