Clpfd - when the 'label()' is necessary? - newbie question

Help!
1

Hello Everybody :slight_smile:

I’m the clpfd newbie and I try to use it to solve the fraction problem from the YT movie:

I’m using: SWI-Prolog version 8.3.17 (but I think it is not very important)
I want the code to give me the exact solution: X = 7, Y = 3

and I’ve found that the code:

(5*X + 3) * (2*Y+1) #= 38*X, [X,Y] ins 3..8.

prints that answer, but the code:

(5*X + 3) * (2*Y+1) #= 38*X, [X,Y] ins 1..10.

does NOT - it requires the label() to be added to work this way…
as here:

(5*X + 3) * (2*Y+1) #= 38*X, [X,Y] ins 1..10, label([X,Y]).

and I do not understand, when the label() is necessary, and when it is optional???
why the first version of my code works ‘out of the box’ and the second doesn’t?

thank you in advance
Tadeusz

1 Like
2

label/1 tells CLP(FD) to find solutions for the given attributed variables; sometimes it isn’t needed, because it’s able to deduce what the solutions are just in the process of setting up the constraints & simplifying.

I’m not sure why changing the domain of X and Y here make it able to deduce the solution right away though; presumably some arcana in the depths of that library…in any case, I always use label/1 (or more typically labeling/2, to specify a search strategy, which can make it find a solution much faster) when dealing with CLP(FD).

1 Like
3

Same here but I found this which may help those seeking a more exact understanding.

?- (5*X + 3) * (2*Y+1) #= 38*X, [X,Y] ins -1..10,label([X,Y]).
X = -1,
Y = 9 ;
X = 7,
Y = 3 ;
false.
1 Like
4

See with [X,Y] ins 3..9. Try it online! In this case, the propagator narrows X down to 7..9 and Y to 3..4. So my understanding is that with [X,Y] ins 3..8, the propagator was able to narrow one of X or Y down to a single value, after which it deduced the other.

1 Like
5

You have performed some arithmetic ‘by hand’, I think, after you found that

?- (5+3//M)*(N+1//2)#=19.
false.

But there is clpBNR, available as a pack, that is able to solve the problem more directly. For instance

?- [library(clpBNR)].
% *** clpBNR v0.9.8alpha ***.
true.

?- [M,N]::integer(0,100),{(5+3/M)*(N+1/2)==19}.
M = 7,
N = 3.

Or better

?- [M,N]::integer,{(5+3/M)*(N+1/2)==19},solve([M,N]).
M = -1,
N = 9 ;
M = 7,
N = 3.

BTW, it’s a pity that the video has such a misleading header. The formula they use as header is indeed

?- [M,N]::integer(0,100),{(5*3/M)*(N*1/2)==19}.
M::integer(0, 30),
N::integer(0, 76).

Now the counterpart of your (fully legitimate!) question could be: why clpBNR doesn’t simply tell us there is no solution ? Seems to be because there are solutions, even for the misleading formula:

?- [M,N]::integer,{(5*3/M)*(N*1/2)==19},solve([M,N]).
M = -28443787120234710,
N = -72057594037927932 ;
M = -28443787120234695,
N = -72057594037927894 ;
...
1 Like
6

Another way of thinking about this is that label/1 forces CLP(FD) to enumerate all the possible values by backtracking. Sometimes, this is needed because there’s no other way of getting a solution; but sometimes it causes a large increase in computation time. In general, you should use label/1 only as a “last resort” for getting a solution because of the potential increase in compute time.

7

True, in fact there are multiple solutions on the range 0..100. That’s one of the uses for “labeling” in clpBNR, to separate those solutions:

?- [M,N]::integer(0,100),{(5*3/M)*(N*1/2)==19},solve(M).
M = N, N = 0 ;
M = 15,
N = 38 ;
M = 30,
N = 76.

So the interval answers from the first query includes all the possible solutions. solve just applies additional constraints in order to separate the solutions. The interesting one is the first: M = N, N = 0. This is presented as a solution because the clpBNR constraint solver cannot disprove that this is a solution (0/0 is undefined).

To get back to the original poster’s question, the general answer (I don’t know much about clpfd internals) is that most constraint systems depend on imperfect/incomplete constraint propagation mechanisms usually because better ones are too computationally expensive. So it’s often necessary to combine them with search strategies like label (and solve). But it is problem dependent; the only way to find out is by trying it.

Also note that it’s easy to implement your own search strategy, e g, in this case between(0,100,M) might do the job just as well.

2 Likes
8

@ridgeworks , thank you very much for clpBNR, it is very well done and well documented. I didn’t know about it until @CapelliC mentioned it. Really appreciate your contribution. Perhaps it should be added to SWI-Prolog.

9

@jamesnvc, @EricGT, @kritixilithos, @CapelliC, @peter.ludemann, @ridgeworks - thank you very much for all the answers, clarifications, and info about the clpBNR library

kind regards
Tadeusz