Search code examples
prologconstraint-programmingclpfdsicstus-prologclpz

Sicstus CLPFD labeling time discrepancy

I was using Sicstus Prolog to solve Advent of Code 2024 Day 13, and I came across a surprising discrepancy in labeling times between different instances of the same constraint model. I have:

minCost(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    P #= A*Ax + B*Bx,
    Cost #= A+B,
    labeling([minimize(Cost)], [A,B,Cost]) -> true; (A=nil, B=nil).

Most instances of this, SAT or UNSAT, are done under 1 miliseconds. For example:

?- minCost(27, 60, 100003443, A, B).
A = 9,
B = 1666720 ?

With fd_statistics showing:

Time:0, Resumps:148, Entailmnts:8, Prunings:157, Backtracks:1, Constrnts:4

But some instances, around 10% of the data set from AoC Day 13, again SAT or UNSAT, take a huge amount of time. For example, this takes almost 3 seconds:

minCost(48, 16, 100017648, A, B).
A = 2083701,
B = 0 ?

With fd_statistics showing:

Time:2722, Resumps:25004424, Entailmnts:8334812, Prunings:27088128, Backtracks:0, Constrnts:4

Note the 10^4-fold increase in resumptions and prunings. Also, A is very high and B is very low, this is a pattern for slow SAT instances. There are plenty slow UNSAT instances, too, for example:

minCost(18, 21, 100001860, A, B).
A = nil,
B = nil ?

with fd_statistics showing:

Time:1273, Resumps:19047989, Entailmnts:2, Prunings:14285996, Backtracks:1, Constrnts:3

I took the same dataset to SWI Prolog's CLPZ, and in total it's faster than Sicstus but more importantly it doesn't have the same discrepancy. I tried a non-prolog solver, called Minion, which performed similar to SWI's CLPZ in total time, and didn't have this wide discrepancy.

My question is, is it normal for constraint solvers to have this much difference in solution times for even such small models? Maybe Sicstus's solver is optimized for small-ish numbers and these large integers are outside that scope? (Note that they're still smaller than Sicstus/CLPFD's largest supported integer). Or did I stumble upon a possible bug?

Note: I tried on Sicstus 4.7.1 and 4.9.0, same issue. The measurements above are from 4.9.0.

Solution

  • I'm the main author of SICStus Prolog.

    You have rediscovered a trait of NP-hard problems: even if average runtimes are small, there are always outlier instances that take a huge amount of time.

    What's surprising in your data are the low backtrack counts. It is as if the search makes no mistakes and all the time is being spent in constraint propagation.

    Something that could contribute to the difference between SICStus and other solvers is your use of A in 0..sup, B in 0..sup, which says that A and B have no upper bounds. Most other solvers either require a given upper bound, or impose some MAXINT bound.

    I've dug a bit deeper now. I'd like to illustrate three points:

    1. Delayed macro expansion.
    2. Searching on the objective.
    3. Value choice heuristic.

    Namely:

    1. Re. P #= A * Ax + B * Bx, which macro expands to two products and one addition. But if Ax and Bx are given in the query, it's better to delay until Ax and Bx are known, because then it can macro expand do a scalar product, which is faster. Delaying can be achieved by call(P #= A * Ax + B * Bx).

    2. Instead of labeling([minimize(Cost)], [A,B,Cost]), you can write labeling([minimize(Cost)], [Cost,A,B]) to make the search go on the cost variable first.

    3. By default, the value choice is a binary choice "split the domain into the min value alone and all the other values". By adding bisect, the choice becomes instead "split the domain into the lower half and the upper half".

    Here are eight variations of your code using these ideas:

    :- use_module(library(clpfd)).

minCost1(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    P #= A*Ax + B*Bx,
    Cost #= A+B,
    labeling([minimize(Cost)], [A,B,Cost]).

minCost2(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    call(P #= A*Ax + B*Bx),
    Cost #= A+B,
    labeling([minimize(Cost)], [A,B,Cost]).

minCost3(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    P #= A*Ax + B*Bx,
    Cost #= A+B,
    labeling([minimize(Cost)], [Cost,A,B]).

minCost4(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    call(P #= A*Ax + B*Bx),
    Cost #= A+B,
    labeling([minimize(Cost)], [Cost,A,B]).

minCost5(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    P #= A*Ax + B*Bx,
    Cost #= A+B,
    labeling([bisect,minimize(Cost)], [A,B,Cost]).

minCost6(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    call(P #= A*Ax + B*Bx),
    Cost #= A+B,
    labeling([bisect,minimize(Cost)], [A,B,Cost]).

minCost7(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    P #= A*Ax + B*Bx,
    Cost #= A+B,
    labeling([bisect,minimize(Cost)], [Cost,A,B]).

minCost8(Ax, Bx, P, A, B) :-
    A in 0..sup, B in 0..sup,
    call(P #= A*Ax + B*Bx),
    Cost #= A+B,
    labeling([bisect,minimize(Cost)], [Cost,A,B]).

    and their run time for minCost(48, 16, 100017648, A, B):

    version runtime
    minCost1 5780
    minCost2 3527
    minCost3 3221
    minCost4 2090
    minCost5 6096
    minCost6 3840
    minCost7 2
    minCost8 4

    Needless to say, constraint programming is a craft. It takes a lot of trial and error to master it.