From: Joachim Schimpf <j.schimpf_at_icparc.ic.ac.uk>

Date: Tue 05 Aug 2003 01:35:07 PM GMT

Message-ID: <3F2FB28B.D7750D2D@icparc.ic.ac.uk>

Date: Tue 05 Aug 2003 01:35:07 PM GMT

Message-ID: <3F2FB28B.D7750D2D@icparc.ic.ac.uk>

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/eclipseReceived on Tue Aug 05 14:36:05 2003

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