Re: Global consistency problem.

Xiao-Hua Kong wrote:
> 
> Hi,
> 
> I wrote a small program as following:
> 
> ########################################
> :-lib(ic).
> 
> case5(LD1,LD2,Va):-
> LD1 = [X1,X2,X3,X4],
> LD2 = [D1,D2],
> LD1 :: [0.0.. 20.0],
> LD2 :: [1.0.. 12.0],
> Va :: 0.0 .. 5.0,
> ic:(X1 =:= 0),
> ic:(X2 =< X1+4),
> ic:(X2 >= X1+2),
> ic:(X3 =:= X1+D1),
> ic:(X4 =:= X2+D2),
> ic:(D1 =< D2+Va),
> ic:(D1 >= D2-Va),
> ic:(X4 =< X3).
> ###################################
> 
> I got result:
> LD1 = [0, X2{2.0 .. 4.0}, X3{3.0 .. 12.0}, X4{3.0 .. 12.0}]
> LD2 = [X3{3.0 .. 12.0}, D2{1.0 .. 10.0}]
> Va = Va{0.0 .. 5.0}

What you have here is NOT a solution. ECLiPSe also tells you:

    There are 5 delayed goals.

which means that several constraints have not been solved yet!

What the result means is: "there may be solutions (none, one or several),
and the solution values for the variables will be within the given ranges".
It does not mean that you can pick arbitrary values in the variable's
domains and get a solution.

In constraint programming, problem solving usually consists of

 - constraint propagation
 - search

Constraint propagation excludes infeasible values from the variable's
domains, but you still need to do search to find actual solutions.
Look at this simple example:

?- [X,Y] :: 1..10, X + Y #= 3.
X = X{[1, 2]}
Y = Y{[1, 2]}
There is 1 delayed goal.
Yes (0.00s cpu)

Constraint propagation has excluded the infeasible values 3..10, but
that still leaves four possible variable assignments (1,1),(1,2),(2,1)
and (2,2) of which only two are actual solutions.

To find these, you have to add search. With integer domains, you can use
labeling/1 or search/6, and that gives you the two concrete solutions:

?- [X,Y] :: 1..10, X + Y #= 3, labeling([X, Y]).
X = 1
Y = 2
More (0.00s cpu)
X = 2
Y = 1
Yes (0.03s cpu)

Because you now have concrete values for the variables, and no leftover
delayed goals, you can be sure that these are actual solutions.
You can find more background in chapter 8 of the ECLiPSe tutorial.

Your example works the same way when you make the variables integral.
With non-integers, you can use locate/2,3,4 and squash/3 to do the
search, but there are additional complications because due to floating
point arithmetic, you can never have a precise solution. This is
discussed in chapter 9 of the ECLiPSe tutorial.

> 
> It seems the result is incorrect (e.g. When Va=0, there exists no
> solution). I guess it is a problem of global consistency, since there are
> several constraints with three variables.
> 
> I have tried using xpress, but it does not help.
> What should I do if I want global consistency with several constraints? Is
> there anything I can use if I change the CSP problem to integer domain?
> 
> Thanks
> Xiaohua
> 
> *************************************************************************
> Xiaohua Kong                    __ O_     Off. : (514)398-3937
> Microelectronics And              // \                398-3055
> Computer System Laboratory       //       Fax  : (514)398-4470
> Department of Electrical &     O /
> Computer Engineering           ------     Email: kong@macs.ece.mcgill.ca
> McGill University, Montreal    ----              kongkonk@hotmail.com
> *************************************************************************

-- 
 Joachim Schimpf              /             phone: +44 20 7594 8187
 IC-Parc                     /      mailto:J.Schimpf@imperial.ac.uk
 Imperial College London    /    http://www.icparc.ic.ac.uk/eclipse