Re: Question on propagation

From: Warwick Harvey <wh_at_icparc.ic.ac.uk>
Date: Tue 05 Jun 2001 02:59:38 PM GMT
Message-ID: <20010605155938.C1227@tempest.icparc.ic.ac.uk>
Hi Tallys,

On Tue, Jun 05, 2001 at 10:35:48AM -0400, Tallys Hoover Yunes wrote:
>    I think I'm about to ask a very basic question,
>    but I couldn't figure out what's going on in the
>    following code.
> 
> 
> [eclipse 3]: [X,Y]::[1..10], #<=(X,Y,B), X #<= Y.
> 
> B = _449{[0, 1]}
> X = _423{[1..10]}
> Y = _436{[1..10]}
> 
> Delayed goals:
>         #>=(_436{[1..10]} - _423{[1..10]}, 0, _449{[0, 1]})
>         _436{[1..10]} - _423{[1..10]}#>=0
> yes.
> 
> 
>    I thought that B would be set to 1. Why not?

Most propagation-based solvers (such as FD) only do local reasoning.  That
is, they consider one constraint at a time only.  Thus the #<=(X, Y, B)
constraint is not aware of the X #<= Y constraint, and only makes deductions
based on the domains of the variables (and in this case, no such deductions
are possible).

>    Is there a way to make this happen without doing search/labeling?

Not with a standard finite domain solver.  If one needs this kind of
reasoning, typically one would either reformulate the problem, write some
new propagators to achieve the desired effect, or use a more sophisticated
constraint solving system which allows this kind of reasoning (cue Thom
Frühwirth to extol the virtues of CHRs :).

Cheers,
Warwick
Received on Tue Jun 05 15:59:47 2001

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