CLP(FD): New labeling/2 behaviour

[Markus Triska-2]

First, the discussed behaviour for labeling/2 is now implemented in the
git master branch. In particular:

   a) several min/max Options can now be specified, and they are worked
      off from left to right (see documentation for details)

   b) inconsistent or repeated other options trigger an error.

Please try it out and let me know if you find any problems. Thanks to
Fernando for his previous comments and suggestions!

Second, I would appreciate your comments and ideas on the following:

The intention is to further reduce domains before the search starts.
Consider for example contracting/1, which users can write themselves:

   contracting(Vs) :- contracting(Vs, Vs).

   contracting([], _).
   contracting([V|Vs], Vars) :-
           fd_inf(V, Min),
           integer(Min),
           (   \+ \+ (V = Min) ->
               fd_sup(V, Max),
               integer(Max),
               (   \+ \+ (V = Max) ->
                   contracting(Vs, Vars)
               ;   V #\= Max,
                   contracting(Vars, Vars)
               )
           ;   V #\= Min,
               contracting(Vars, Vars)
           ).

The idea here is to consider a list of finite domains variables, and to
contract the domain of each variable by removing elements that are
immediately seen to be inconsistent after unification, but for which
propagation in itself is not strong enough to determine this without
trying the actual value first. contracting/1 can be used immediately
before labeling/2, and can help to more accurately assess the domains of
all variables, which is important in many labeling strategies.

As an example, consider the following query:

   ?- Vs = [X,Y,Z], Vs ins 100..500, X*X*X + Y*Y #= Z*Z*Z.
   %@ Z in 100..500,
   %@ Y in 100..500,
   %@ X in 100..500,
   %@ etc.

and now with contracting/1:

   ?- Vs = [X,Y,Z], Vs ins 100..500, X*X*X + Y*Y #= Z*Z*Z, contracting(Vs).
   %@ Z in 101..250,
   %@ Y in 100..500,
   %@ X in 100..249,
   %@ etc.

Many domain elements could be removed at the boundaries. Then try
labeling([ff], Vs) to find all solutions and see the difference.

You can think of contracting/1 as a kind of "anti"-labeling, where you
want to find *in*consistent values. Except that it doesn't (currently)
generate alternative solutions, so you can use it every time before you
label without creating redundant solutions.

The details of how this should be integrated in library(clpfd) are still
open: It could be a labeling option, a separate predicate etc. There are
also various "strengths" for this anti-labeling: One could easily extend
it to search for inconsistent values inside domains instead of only at
the boundaries. The way to determine a fix-point can also vary: The
current method was suggested by Ulrich and has interesting properties,
though it's clear that there are many other ways to do it. In any case,
I hope you'll find it interesting and experiment a bit with it.

All the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...