[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Problem with CLP

From: Manuel Carro
Subject: Re: Problem with CLP
Date: Wed, 24 Sep 2003 00:28:11 +0200

>> There's the rub. GNU Prolog is reporting the current domain of the
>> constrained variables. You need to try instantiating the variables to
>> determine if the domain is a solution. It has been a while since I
>> wrote a gprolog program, but search for labeling (labelling?) in the
>> documentation.

    In general, it is not that straightforward; it can be done, but
the whole program may need to be transformed.  Lars did not want to
resort to labeling due to efficiency reasons.  If we admit the use of
labeling as in, e.g.,

 ?- p(X, Y), labeling([X, Y]).

(I may not be using the exact syntax & predicate names as Gnu Prolog),
an answer which makes [X, Y] ground is not necessarily a solution for
p(X, Y): take p/2 to be, e.g.,

 p(X, Y):-
     X in 0..1000,
     Y in 0..1000,
     Z*Z*Z*Z*Z  #= X,
     Z*Z*Z*Z*Z  #= Y.

where the expressions involving Z are chosen so that they are
complicated enough to make propagation useless.  Assigning a value to
X will not (necessarily) bind Z, and the same happens with Y.  So, for
example (while this is not a Gnu Prolog execution, the idea still

 | ?- p(X, Y), labeling([X, Y]).
 X = 0, Y = 0 ? ;

 X = 0, Y = 1 ? ;

 X = 0, Y = 2 ? ;

 X = 0, Y = 3 ? ;


    But these are not real solutions when you look at what p/2 means.
Enumerating Z would overcome this, but you do not have (direct) access
to Z from outside p/2 unless this is explicitly returned.  As Fergus
suggested, call_residue/2 would do this.  Other constraint systems,
such as CLP(R), can return an answer constraint as

 -X + A^5.0 = 0.0, -Y+ A^5.0 = 0.0

to the same query because they perform a projection of the constraint
store.  If X and/or Y are later assigned a value, the constraint store
gets simplified and one can see this behavior:

 ?- p(X, Y), {X = 0, Y = 1}.


while with CLP(FD) one gets (as we've seen)

 | ?- p( X, Y ) , X #= 0, Y #= 1.

 X = 0, Y = 1 ? 

One reason for this difference is that projecting constraints is very
costly in CLP(FD).  If the non-ground variables (inernally) involved
in a query are returned, this will allow a user to enumerate them or,
at least, to deduce that a "yes" answer is might be a "maybe" answer.

    Hope this helps. Cheers,
|Manuel Carro -- Facultad de Informática -- U. Politécnica de Madrid (UPM) |
|mcarro_at_fi_dot_upm_dot_es --- Ph: +34-91336-7455 --- FAX: +34-91336-7412|
| ---|

reply via email to

[Prev in Thread] Current Thread [Next in Thread]