From: Warwick Harvey <wh_at_icparc.ic.ac.uk>

Date: Thu 04 Apr 2002 05:11:03 PM GMT

Message-ID: <20020404181103.C49@tempest.icparc.ic.ac.uk>

Date: Thu 04 Apr 2002 05:11:03 PM GMT

Message-ID: <20020404181103.C49@tempest.icparc.ic.ac.uk>

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, WarwickReceived on Thu Apr 04 18:12:18 2002

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:13 PM GMT GMT
*