clpfd - 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
    ).