Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

PROLOG CLPFD How to express this via constraints?

Given the following sample of code:

example(Ls) :-
    Ls = [X,Y],
    Ls ins 1..2,
    Cost #= max((X #= 1)*3 + (Y #= 1)*5,
                (X #= 2)*3 + (Y #= 2)*5),
    labeling([minimize(Cost)], Ls).

The idea is to find the assignment to variables of Ls that minimizes Cost (in this simple example, it would be either X=1 and Y=2, or X=2 and Y=1).

I am trying to use the fact that the constraint #=/2 is reifiable, which means reflecting their truth values into Boolean values represented by the integers 0 and 1. (taken from the manual http://www.swi-prolog.org/man/clpfd.html).

However, it doesn't work. I get the following error:

ERROR: Domain error: `clpfd_expression' expected, found `_G3154#=1'

What would be an equivalent, correct version?

like image 444
user2460978 Avatar asked Jan 12 '14 13:01

user2460978


2 Answers

Reification involves separate constraints (#<==>/2, #==>/2 etc.), you can use them for example like:

example(Ls) :-
    Ls = [X,Y],
    Ls ins 1..2,
    X #= 1 #<==> B1,
    Y #= 1 #<==> B2,
    X #= 2 #<==> B3,
    Y #= 2 #<==> B4,
    Cost #= max(B1*3 + B2*5, B3*3 + B4*5),
    labeling([min(Cost)], Ls).

Sample query and its result:

?- example(Ls).
Ls = [1, 2] ;
Ls = [2, 1] ;
Ls = [1, 1] ;
Ls = [2, 2] ;
false.
like image 143
mat Avatar answered Sep 28 '22 07:09

mat


As an alternative to using reification you could also use additional arithmetic constraints for "capturing" equality in an expression:

example([X,Y]) :-
    X in 1..2,
    Y in 1..2,
    Cost #= max(3*(1-min(1,abs(X-1))) + 5*(1-min(1,abs(Y-1))),
                3*(1-min(1,abs(X-2))) + 5*(1-min(1,abs(Y-2)))),
    labeling([min(Cost)], [X,Y]).

Note that the expression inside Cost #= max(...) can be slightly simplified.

Sample use:

?- example(Ls).
  Ls = [1,2]
; Ls = [2,1]
; Ls = [1,1]
; Ls = [2,2]
; false.
like image 32
repeat Avatar answered Sep 28 '22 08:09

repeat