Re: [eclipse-clp-users] Two problems with the ic-Solver

Andreas Berger wrote:

> 1.
> The following code shows the behaviour of ic, when giving it two mutual 
> exclusive Constraints at the ECLiPSe commandline. In this case I just 
> wan't to know if the given CSP is solveable. (ic library is loaded).
> 
> /[eclipse 2]: A #< B, A #> B.
> 
> A = A{-1.0Inf .. 1.0Inf}
> B = B{-1.0Inf .. 1.0Inf}
> 
> 
> Delayed goals:
>     B{-1.0Inf .. 1.0Inf} - A{-1.0Inf .. 1.0Inf} #> 0
>     -(B{-1.0Inf .. 1.0Inf}) + A{-1.0Inf .. 1.0Inf} #> 0
> Yes (0.00s cpu)
> /
> Why does the solver say it's possible to solve something like this?
> 

ECLiPSe is saying that there may be a solution, subject to the 
constraints being true.

Your question however touches on some basic issues with constraint 
programming. I can only give very brief answers here, you should read 
books on constraint programming to get a more detailed view.

The specific example here is a well known illustration of a
weakness of local propagation based solvers -- reasoning is done for 
each constraint, and there is no "global" reasoning that looks at all 
the constraints at the same time, i.e. the solver does not have any 
mechanism to see immediately that these two constraints are inconsistent.

For your specific case here, if you do not place any domain on your 
variables, then no reasoning can be done at all for either constraints.

> At the second step when I try to get a specific solution for the problem 
> with locate, ECLiPSe gets in an infinite loop and does not return anymore.
> 
> /[eclipse 3]: A #< B, A #> B, locate([A,B],0.1)./
> 
> 
> Why? How can i avoid this?
> 

Normally, if you are working with floats, you should use the real 
variants of the constraints ($</2, $>/2). Also if you want to use
the search predicates (like locate/2), your variables should be given
a finite interval (the smaller the better).

More generally, for local propagation solvers, the detection of 
inconsistency for these constraints will be slow, because each time the 
constraint is invoked, it is only able to trim the interval by a little 
(1 if you are using finite domain), and this trimming continues until 
you have reduced one of the variables to empty, when the inconsistency 
is detected.

For your specific example, there is probably no way to avoid this 
problem, unless you know that you are likely to post such mutually 
inconsistent constraints, in which case you can always check if you have 
posted the "partner" constraint already when you post one of these 
constraints.

More generally, you can try to write one constraint that captures the 
meaning of two or more simpler constraints.

If your problem will really benefit with some more "global" reasoning 
about all your constraints at the same time, you may want to look at 
using other solving methods for your problem, for example, Mathematical 
Programming based approaches. lib(eplex) lets you use MP solvers with 
ECLiPSe, and the sort of inconsistency you have is detected very easily.

Cheers,

Kish
-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.