PROLOG CLPFD How to express this via constraints?

Question

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?

Breeden

Answer 1

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.

Beaudoin

Is there any way to the same without using the intermediate variables B1..B4? In the real program, there would be over 200 of them. – Breeden

I have used as many as 10,000 such intermediate variables (for example, for animating the search process when solving the 100-queens problem on a 100x100 chessboard) without any problems. So, I suggest you first try whether it works, and try to find more efficient formulations only if you really need them. Of course, in a larger example, you do not manually introduce these intermediate variables, but set them up for example via an auxiliary predicate that relates them to the list of variables and values via some input data you specify or compute. – Beaudoin

Using the method in your example, I got it to work. However, with over 10 variables in Ls and 7 posible values for each element, it takes over a minute to finish. – Breeden

So the usual ways to make it faster apply: First, I would try a different labeling strategy, like ff: labeling([min(Cost),ff], Ls). I would then experiment also with other options, like down, bisect etc. Please keep in mind that you are already trying to solve a problem over a search space of potential size 10^7 = 10,000,000, and whether or not you have 100 or 1000 additional auxiliary variables will not affect this. You may, however, be able to find a stronger formulation or stronger constraints so that the search space can be further reduced, which will typically help a lot more. – Beaudoin

I meant 7^10 = 282,475,249. – Beaudoin

Answer 2

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.

Hallucinate