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

From: Andreas Berger <bergeand_at_tu-cottbus.de>
Date: Fri, 12 Feb 2010 14:28:17 +0100
Ok, thank you very much, now I understand why it does not work. I've now 
tried to place a domain on the variables and it works of course.
But I think the better way in my position is to filter out such 
inconsistent constraints before giving them to eclipse, because i can 
not estimate the domain size.

Andreas

Kish Shen schrieb:
> 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
Received on Fri Feb 12 2010 - 13:29:10 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET