Enumeration Predicates (SICStus Prolog)

10.10.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. Assigns, in increasing order via backtracking, a feasible value to X.

labeling(:Options, +Variables)

where Variables is a list of domain variables 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, then 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), then 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, then 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), then 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 do not 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, then 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, but have no effect on the semantics or on the meaning of other options:

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)

See lib-timeout. Time should be an integer number of milliseconds. If the search is exhausted within this time and no solution is found, then the search merely fails, as usual. Otherwise, Flag is bound to a value reflecting the outcome:

optimality since release 4.4: If best was selected in an optimization problem, then the search space was exhausted, having found the optimal solution. The variables are bound to the corresponding values. If best was not selected, this flag value is not used.
success since release 4.4: If best was selected in an optimization problem, then the search timed out before the search space was exhausted, having found at least one solution. If best was not selected, then a solution was simply found before the time limit. In any case, the variables are bound to the values corresponding to the latest solution found.
time_out since release 4.4: If best was selected in an optimization problem, then the search timed out before any solution was found. If best was not selected, then the search timed out while searching for the next solution. The variables are left unbound.

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

To give a time budget and collect the solutions of a satisfiability problem up to the time limit, use:

| ?- constraints(Variables),
     findall(Variables, labeling([time_out(Budget,success)|Options]), Solutions).

where Flag=success will hold if all solutions were found, and Flag=time_out will hold if the time expired.

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 has been lifted 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.