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)
maximize(
:Goal,
?X)
Uses a branch-and-bound algorithm with restart 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, at
which time Goal and X are unified with values
corresponding to the optimal solution.
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), and whether all solutions or a
single, optimal solution should be found. The options are divided into
four groups. One option may be selected per group. Also, the number of
assumptions (choices) made during the search can be collected. Finally,
a discrepancy limit can be imposed.
leftmost
min
max
ff
ffc
variable(
Sel)
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
X #=
B
and
X #\=
B
, where B is the lower or upper
bound of X. This is the default.
enum
bisect
X #=<
M
and
X #>
M
, where M is the midpoint
of the domain of X. This strategy is also known as domain
splitting.
value(
Enum)
Enum is expected to succeed nondeterminately, narrowing the
domain of X, and to backtrack one or more times, providing
alternative narrowings. 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
down
The following options control whether all solutions should be enumerated by backtracking or whether a single solution that minimizes (maximizes) X is returned, if one exists.
all
minimize(
X)
maximize(
X)
Uses a branch-and-bound algorithm to find an assignment that minimizes (maximizes) the domain variable X. The labeling should constrain X to become assigned for all assignments of Variables.
Also, 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, a limit on the discrepancy of the search 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.
For example, to enumerate solutions using a static variable ordering, use:
| ?- constraints(Variables), labeling([], Variables). %same as [leftmost,step,up,all]
To minimize a cost function using branch-and-bound search, 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.
As opposed to the predicates above, which search for consistent assignments to domain variables, the following predicate searches for a consistent ordering among tasks competing for an exclusive resource, without necessarily fixing their start times:
order_resource(
+Options,
+Resource)
where Options is a list of search options and Resource
represents a resource as returned by serialized/3
(see Combinatorial Constraints) on which tasks must be serialized.
True if a total ordering can be imposed on the tasks, enumerating all
such orderings via backtracking.
The search options control the construction of the total ordering. It may contain at most one of the following atoms, selecting a strategy:
first
last
and at most one of the following atoms, controlling which task to
select at each step. If first
is chosen (the default), the task
with the smallest value is selected; otherwise, the task with the
greatest value is selected.
est
lst
ect
lct
[first,est]
(the default) and [last,lct]
can be good heuristics.