Re: Global consistency problem.

Hi Joachim,

Thanks for you answer.
I am a new user in CLP. My target is to decide the range of a variable (say
Va in my small example), so that there exists solution for the CSP problem.
That's why the solution with the range of the variable is better than
discrete values (such as, by using labeling). Is there any way I can do to
find the range of a variable if the constraints are linear?

Thanks
Xiaohua

----- Original Message -----
From: "Joachim Schimpf" <j.schimpf@icparc.ic.ac.uk>
To: <eclipse-users@icparc.ic.ac.uk>
Sent: Tuesday, August 05, 2003 9:35 AM
Subject: Re: [eclipse-users] 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
>