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.