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

Hello Everybody 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?

1 Like

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

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

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

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

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.

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

@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.

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

kind regards