Prolog manual or custom labeling

Question

I am currently writing a solver for a floor planning problem in Prolog and have some issues with the labeling part.

The current problem is my constraints are posted but when I launch the labeling, it takes forever to find a solution. I would like to bring in some heuristics.

My question is, how do I manually label my variables ? I am afraid that after defining a clpfd variable like this :

X in Xinf..Xsup

and constraining it, If I do something like :

    fd_sup(X, Xmax),
    X = Xmax,
...

in my custom label, I won't be using the backtrack ability of Prolog to test the other values of X's domain. Am I wrong ?

Also, is there a smarter way to label my variables than writing custom labeling procedures ? My idea of heuristics would consist in trying extrema of a variable domain alternatively (like max(X), min(X), max(X-1), min(X-1) etc...)

Hope you can help me :)

Answer 1

It is not difficult to write a custom labeling procedure, and with most real problems you will eventually need one anyway in order to incorporate problem-specific heuristics.

The two main components of a labeling procedure are

1. variable selection: from all the remaining (i.e. not yet instantiated) problem variables, pick one to consider next.
2. value selection or branching: explore, via backtracking, two or more alternative sub-problems by reducing the chosen variable's domain in (usually) complementary ways.

Using this scheme, the default labeling procedure can be written as

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         label(Xs1)
    ;
         true    % done, no variables left
    ).

select_variable(X, [X|Xs], Xs).     % 'leftmost' strategy

branch(X) :- indomain(X).

You can now redefine select_variable/3 to implement techniques such as "first-fail", and redefine branch/1 to try domain values in different orders. As long as you make sure that branch/1 enumerates all of X's domain values on backtracking, your search remains complete.

Sometimes you want to try just one domain value first (say, one suggested by a heuristics), but, if it is no good, not commit to another value immediately. Let's say that, as in your example, you want to try the maximum domain value first. You could write this as

branch(X) :-
    fd_sup(X, Xmax),
    (
         X = Xmax           % try the maximum
    ;
         X #\= Xmax         % otherwise exclude the maximum
    ).

Because the two cases are complementary and cover all possible values for X, your search is still complete. However, because of the second alternative, branch/1 can now succeed with an uninstantiated X, which means you must make sure in the labeling procedure that you don't lose this variable from your list. One possibility would be:

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         ( var(X) -> append(Xs1, [X], Xs2) ; Xs2=Xs1 ),
         label(Xs2)
    ;
         true    % done, no variables left
    ).

Answer 2

First, always try built-in heuristics. ff is often a good strategy.

For custom labeling strategies, it is often easiest to first convert the domain to a list, then reorder the list, and then simply use member/2 to assign the values of the domain using the new order.

A good building black is dom_integers/2, relating a finite CLP(FD) domain to a list of integers:

:- use_module(library(clpfd)).

dom_integers(D, Is) :- phrase(dom_integers_(D), Is).

dom_integers_(I)      --> { integer(I) }, [I].
dom_integers_(L..U)   --> { numlist(L, U, Is) }, Is.
dom_integers_(D1\/D2) --> dom_integers_(D1), dom_integers_(D2).

Your specific strategy is easily expressed on a list of such ordered integers, relating these integers to a second list where the values occur in the order you describe:

outside_in([]) --> [].
outside_in([I]) --> [I].
outside_in([First|Rest0]) --> [First,Last],
        { append(Rest, [Last], Rest0) },
        outside_in(Rest).

Sample query and result:

?- phrase(outside_in([1,2,3,4]), Is).
Is = [1, 4, 2, 3] ;
false.

Combining this with fd_dom/2 and dom_integers/2, we get (bindings for variables other than X omitted):

?- X in 10..20,
   fd_dom(X, Dom),
   dom_integers(Dom, Is0),
   phrase(outside_in(Is0), Is),
   member(X, Is).
X = 10 ;
X = 20 ;
X = 11 ;
X = 19 ;
X = 12 ;
X = 18 ;
etc.

Nondeterminism is preserved by member/2.

Answer 3

Make sure to distinguish labeling strategies from additional propagation. These two aspects are currently a bit mixed in your question.

In SWI-Prolog, there is a predicate called clpfd:contracting/1. It does what you describe: It tries values from the domain boundaries, and removes values that can be seen as inconsistent, i.e., for which it is known that no solution exists.

Therefore, if you have a list of variables Vs, you can try: clpfd:contracting(Vs), and see if this helps.

Note that this can also significantly slow down the search, though on the other hand, also help significantly to reduce the search space before even trying any labeling!

Answer 4

To complement the other answers (one contrasting labeling and propagation, one showing a dedicated labeling method), I now tackle a further very important aspect of this question:

Very often, when beginners complain about the speed of their code, it turns out that their code in fact doesn't even terminate! More efficiency would not help in that case.

Hence, this answer points you towards first ensuring actual termination of your relation.

The best way to ensure termination of CLP(FD) programs is to separate them into 2 parts:

1. the first, called the core relation, simply posts all constraints.
2. the second uses labeling/2 to perform the actual search.

Have you done this in your program? If not, please do. When this is done, make sure that the core relation, say solution/2 (where the arguments are: a term denoting the task instance, and the list of variables to be labeled) terminates universally by querying:

?- solution(Instance, Vs), false.

If this terminates, then the following also terminates:

?- solution(Instance, Vs), label(Vs), false.

Of course, in larger tasks, you have no chance to actually witness the termination of the latter query, but a good chance to witness the termination of the first query, because setting up the constraints is often much faster than actually obtaining even a a single solution.

Therefore, test whether your core relation terminates!

Answer 5

This follows up on this previous answer by @mat.

If you have got some more CPU cycles to burn, try shave_zs/1 as defined in this previous answer.

shave_zs/1 kind of works like the auxiliary library predicate clpfd:contracting/1. Unlike contracting/1, however, all values are "up for grabs"—not just the ones at the boundary. YMMV!