10.35.5 Enumeration Predicates

As is usually the case with finite domain constraint solvers, this solver is not complete. That is, it does not ensure that the set of posted constraints is satisfiable. One must resort to search (enumeration) to check satisfiability and get particular solutions.

The following predicates provide several variants of search:

indomain(?X)
where X is a domain variable with a bounded domain or an integer. Assigns, in increasing order via backtracking, a feasible value to X.
labeling(:Options, +Variables)
where Variables is a list of domain variables or integers and Options is a list of search options. The domain variables must all have bounded domains. True if an assignment of the variables can be found, which satisfies the posted constraints.
first_bound(+BB0, -BB)
later_bound(+BB0, -BB)
Provides an auxiliary service for the value(Enum) option (see below).
minimize(:Goal,?X)
minimize(:Goal,?X,+Options)   since release 4.3
maximize(:Goal,?X)
maximize(:Goal,?X,+Options)   since release 4.3
Uses a restart algorithm to find an assignment that minimizes (maximizes) the domain variable X. Goal should be a Prolog goal that constrains X to become assigned, and could be a labeling/2 goal. The algorithm calls Goal repeatedly with a progressively tighter upper (lower) bound on X until a proof of optimality is obtained.

Whether to enumerate every solution that improves the objective function, or only the optimal one after optimality has been proved, is controlled by Options. If given, it whould be a list containing a single atomic value, one of:

best   since release 4.3
Return the optimal solution after proving its optimality. This is the default.
all   since release 4.3
Enumerate all improving solutions, on backtracking seek the next improving solution. Merely fail after proving optimality.

The Options argument of labeling/2 controls the order in which variables are selected for assignment (variable choice heuristic), the way in which choices are made for the selected variable (value choice heuristic), whether the problem is a satisfaction one or an optimization one, and whether all solutions or only the optimal one should be returned. The options are divided into five groups. One option may be selected per group. Also, the number of assumptions (choices) made during the search can be counted. Finally, limits on the execution time and discrepancy of the search can be imposed:

The following options control the order in which the next variable is selected for assignment.
leftmost
input_order
The leftmost variable is selected. This is the default.
min
smallest
The leftmost variable with the smallest lower bound is selected.
max
largest
The leftmost variable with the greatest upper bound is selected.
ff
first_fail
The first-fail principle is used: the leftmost variable with the smallest domain is selected.
anti_first_fail   since release 4.3
The leftmost variable with the largest domain is selected.
occurrence   since release 4.3
The leftmost variable among those that have the most constraints suspended on it is selected.
ffc
most_constrained
The most constrained heuristic is used: a variable with the smallest domain is selected, breaking ties by (a) selecting the variable that has the most constraints suspended on it and (b) selecting the leftmost one.
max_regret   since release 4.3
The variable with the largest difference between its first two domain elements is selected. Ties are broken by selecting the leftmost variable.
variable(Sel)
Sel is a predicate to select the next variable. Given Vars, the variables that remain to label, it will be called as Sel(Vars,Selected,Rest).

Sel is expected to succeed determinately, unifying Selected and Rest with the selected variable and the remaining list, respectively.

Sel should be a callable term, optionally with a module prefix, and the arguments Vars,Selected,Rest will be appended to it. For example, if Sel is mod:sel(Param), it will be called as mod:sel(Param,Vars,Selected,Rest).

The following options control the way in which choices are made for the selected variable X:

step
Makes a binary choice between X #= B and X #\= B, where B is the lower or upper bound of X. This is the default.
enum
Makes a multiple choice for X corresponding to the values in its domain.
bisect
Makes a binary choice between X #=< M and X #> M, where M is the middle of the domain of X, i.e. the mean of min(X) and max(X) rounded down to the nearest integer. This strategy is also known as domain splitting.
median   since release 4.3
Makes a binary choice between X #= M and X #\= M, where M is the median of the domain of X. If the domain has an even number of elements, the smaller middle value is used.
middle   since release 4.3
Makes a binary choice between X #= M and X #\= M, where M is the middle of the domain of X, i.e. the mean of min(X) and max(X) rounded down to the nearest integer.
value(Enum)
Enum is a predicate that should prune the domain of X, possibly but not necessarily to a singleton. It will be called as Enum(X,Rest,BB0,BB) where Rest is the list of variables that need labeling except X, and BB0 and BB are parameters described below.

Enum is expected to succeed nondeterminately, pruning the domain of X, and to backtrack one or more times, providing alternative prunings. To ensure that branch-and-bound search works correctly, it must call the auxiliary predicate first_bound(BB0,BB) in its first solution. Similarly, it must call the auxiliary predicate later_bound(BB0,BB) in any alternative solution.

Enum should be a callable term, optionally with a module prefix, and the arguments X,Rest,BB0,BB will be appended to it. For example, if Enum is mod:enum(Param), it will be called as mod:enum(Param,X,Rest,BB0,BB).

The following options control the order in which the choices are made for the selected variable X. Not useful with the value(Enum) option:

up
The domain is explored in ascending order. This is the default.
down
The domain is explored in descending order.

The following options tell the solver whether the given problem is a satisfaction problem or an optimization problem. In a satisfaction problem, we wish to find values for the domain variables, but we don't care about which values. In an optimization problem, we wish to find values that minimize or maximize some objective function reflected in a domain variable:

satisfy   since release 4.3
We have a satisfication problem. Its solutions are enumerated by backtracking. This is the default.
minimize(X)
maximize(X)
We have an optimization problem, seeking an assignment that minimizes (maximizes) the domain variable X. The labeling should constrain X to become assigned for all assignments of Variables. It is useful to combine these option with the time_out/2, best, and all options (see below). If these options occur more than once, the last occurrence overrides previous ones.

The following options are only meaningful for optimization problems. They tell the solver whether to enumerate every solution that improves the objective function, or only the optimal one after optimality has been proved:

best   since release 4.3
Return the optimal solution after proving its optimality. This is the default.
all   since release 4.3
Enumerate all improving solutions, on backtracking seek the next improving solution. Merely fail after proving optimality.

The following options are only meaningful for optimization problems. They tell the solver what search scheme to use:

bab   since release 4.3
Use a branch-and-bound scheme, which incrementally tightens the bound on the objective as more and more solutions are found. This is the default, and is usually the more efficient scheme.
restart   since release 4.3
Use a scheme that restarts the search with a tighter bound on the objective each time a solution is found.

The following option counts the number of assumptions (choices) made during the search:

assumptions(K)
When a solution is found, K is unified with the number of choices made.

Finally, limits on the discrepancy of the search and the execution time can be imposed:

discrepancy(D)
On the path leading to the solution there are at most D choicepoints in which a non-leftmost branch was taken.
time_out(Time,Flag)
If combined with the best, bab, and minimize(V) or maximize(V) options, and the time limit Time in milliseconds is reached, then (if at least one solution was found, then Flag, Variables and V are respectively unified with time_out and the values of the best solution found, else the search merely fails). If used otherwise, equivalent to a goal time_out(labeling(...),Time,Flag) (see lib-timeout).

For example, to enumerate solutions using a static variable ordering, use:

     | ?- constraints(Variables),
          labeling([], Variables).
          %same as [leftmost,step,up,satisfy]

To minimize a cost function using branch-and-bound search, computing the best solution only, with a dynamic variable ordering using the first-fail principle, and domain splitting exploring the upper part of domains first, use:

     | ?- constraints(Variables, Cost),
          labeling([ff,bisect,down,minimize(Cost)], Variables).

The file library('clpfd/examples/tsp.pl') contains an example of user-defined variable and value choice heuristics.

Note that, when used for optimization, labeling/2 has a limitation compared to minimize/[2,3] and maximize/[2,3]: the variable and value choice heuristics specified by labeling/2 must apply to the whole set of variables, with no provision for different heuristics for different subsets. As of release 4.3, this limitation is overcome by the following predicate:

solve(:Options, :Searches)   since release 4.3
where Options is a list of options of the same shape as taken by labeling/2, and Searches is a list of labeling/2 and indomain/1 goals, or a single such goal. The domain variables of Searches must all have bounded domains. True if the conjunction of Searches is true.

The main purpose of this predicate is for optimization, allowing to use different heuristics in the different Searches. For satisfiability problems, a simple sequence of labeling/2 and indomain/1 goals does the trick.

The treatment of the Options, as well as the suboption lists given in the labeling/2 goals of Searches, is a bit special. Some options are global for the whole search, and are ignored if they occur in the suboption lists. Others are local to the given labeling/2 goal, but provides a default value for the whole search if it occurs in Options. The following table defines the role of each option as global or local:

all global
anti_first_fail local
assumptions/1 global
bab global
best global
bisect local
discrepancy/1 local
down local
enum local
ffc local
ff local
first_fail local
input_order local
largest local
leftmost local
maximize/1 global
max local
max_regret local
median local
middle local
minimize/1 global
min local
most_constrained local
occurrence local
restart global
satisfy global
smallest local
step local
time_out/2 global
up local
value/1 local
variable/1 local

For example, suppose that you want to minimize a cost function using branch-and-bound search, enumerating every improving solution, using left-to-right search on some variables followed by first-fail domain splitting search on some other variables. This can be expressed as:

     | ?- constraints([X1,X2,X3,Y1,Y2,Y3], Cost),
          solve([minimize(Cost),all],
                [labeling([leftmost],[X1,X2,X3]),
                 labeling([ff,bisect],[Y1,Y2,Y3])]).

Send feedback on this subject.