Re: Delayed goals

From: Joachim Schimpf <J.Schimpf_at_icparc.ic.ac.uk>
Date: Mon 20 Dec 1999 04:22:07 PM GMT
Message-ID: <385E57AF.98AA0F65@icparc.ic.ac.uk>
Doug Edmunds wrote:
> 
> /*How do I overcome the
> delayed goals in this code, to
> get the desired result
> X=130, Y =70, Z = 80?
> 
> Doug Edmunds
> 16 Dec 1999
> */
> 
> :-lib(fd).
> 
> g :- X #>0, Y#>0, Z #>0,
> X + Y + Z #= 280,
> X #= 130,
> Y #= Z - 10.
> 
> Additional comment:
> 
> I added a line
> indomain(Y),
> at the end, and it produces the correct answer.


What you are observing here is a manifestation of a fundamental
property of the constraint programming paradigm:

The implementation of the constraints is "incomplete" and you
need to add search in order to establish the existence (and the
actual values) of solutions.

Why is this so? Because _in_general_ there are no known efficient
algorithms to solve a given set of constraints. The implementation
of the constraints therefore restricts itself to infer consequences
(ie. find inconsistencies and bound reductions) that can be found
using efficient (polynomial complexity) algorithms. So you can rely
on the constraints to _help_ you find a solution, but in most cases
they won't do all the work...

Now, your example of course happens to be one of the cases where we do
know an efficient algorithm to solve the whole problem: the type of
constraints is very restricted, they are all linear equations and we
could simply do Gauss-elimination. However, the fd-library does not
implement that, it only implements domain propagation, which is weaker
on linear equations but applicable to a wider range of constraints.

Other libraries like lib(clpr) or lib(eplex) can solve that directly:

[eclipse 1]: lib(clpr). 
...
yes.
[eclipse 2]: X$>=0, Y$>=0, Z$>=0, X + Y + Z $= 280, X$=130, Y$=Z-10.

X = 130.0
Y = 70.0
Z = 80.0
yes.

------------------------------------------------------------------------
 Joachim Schimpf                /               phone: +44 171 594 8187
 IC-Parc, Imperial College     /              mailto:J.Schimpf@ic.ac.uk
 London SW7 2AZ, UK           /      http://www.icparc.ic.ac.uk/eclipse
Received on Mon Dec 20 16:28:26 1999

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