next up previous index
Next: Arithmetic Constraint Predicates Up: The Finite Domains Library Previous: Terminology   Index

Constraint Predicates

?Vars :: ?Domain
Vars is a variable or a list of variables with the associated domain Domain. Domain can be a closed integer interval denoted as Min .. Max, or a list of intervals and/or atomic or ground elements. Although the domain can contain any compound terms that contain no variable, the functor ../2 is reserved to denote integer intervals and thus 1..10 always means an interval and a..b is not accepted as a compound domain element.

If Vars is already a domain variable, its domain will be updated according to the new domain; if it is instantiated, the predicate checks if the value lies in the domain. Otherwise, if Vars is a free variable, it is converted to a domain variable. If Vars is a domain variable and Domain is free, it is bound to the list of elements and integer intervals representing the domain of the variable (see also dvar_domain/2 which returns the actual domain).

When a free variable obtains a finite domain or when the domain of a domain variable is updated, the constrained list of its suspend attribute is woken, if it has one.

integers(+Vars)
This constrains the list of variables Vars to have integer domains. Any non-domain variables in Vars will be given the default integer domain.

::(?Var, ?Domain, ?B)
B is equal to 1 iff the domain of the finite domain variable Var is a subset of Domain and 0 otherwise.

atmost(+Number, ?List, +Val)
At most Number elements of the list List of domain variables and ground terms are equal to the ground value Val.

constraints_number(+DVar, -Number)
Number is the number of constraints and suspended goals currently attached to the variable DVar. Note that this number may not correspond to the exact number of different constraints attached to DVar, as goals in different suspending lists are counted separately. This predicate is often used when looking for the most or least constrained variable from a set of domain variables (see also deleteffc/3).

element(?Index, +List, ?Value)
The Index'th element of the ground list List is equal to Value. Index and Value can be either plain variables, in which case a domain will be associated to them, or domain variables. Whenever the domain of Index or Value is updated, the predicate is woken and the domains are updated accordingly.

fd_eval(+E)
The constraint expression E is evaluated on runtime and no compile-time processing is performed. This might be necessary in the situations where the default compile-time transformation of the given expression is not suitable, e.g. because it would require type or mode information.

indomain(+DVar)
This predicate instantiates the domain variable DVar to an element of its domain; on backtracking the subsequent values are taken. It is used, for example, to find a value of DVar which is consistent with all currently imposed constraints. If DVar is a ground term, it succeeds. Otherwise, if it is not a domain variable, an error is raised.

is_domain(?Term)
Succeeds if Term is a domain variable.

is_integer_domain(?Term)
Succeeds if Term is an integer domain variable.

min_max(+Goal, ?C)
If C is a linear term, a solution of the goal Goal is found that minimises the value of C. If C is a list of linear terms, the returned solution minimises the maximum value of terms in the list. The solution is found using the branch and bound method; as soon as a partial solution is found that is worse than a previously found solution, failure is forced and a new solution is searched for. When a new better solution is found, the bound is updated and the search restarts from the beginning. Each time a new better solution is found, the event 280 is raised. If a solution does not make C ground, an error is raised, unless exactly one variable in the list C remains free, in which case the system tries to instantiate it to its minimum.

minimize(+Goal, ?Term)
Similar to min_max/2, but Term must be an integer domain variable. When a new better solution is found, the search does not restart from the beginning, but a failure is forced and the search continues. Each time a new better solution is found, the event 280 is raised. Often minimize/2 is faster than min_max/2, sometimes min_max/2 might run faster, but it is difficult to predict which one is more appropriate for a given problem.

min_max(+Goal, ?Template, ?Solution, ?C)
minimize(+Goal, ?Template, ?Solution, ?Term)
Similar to min_max/2 and minimize/2, but the variables in Goal do not get instantiated to their optimum solutions. Instead, Solutions will be unified with a copy of Template where the variables are replaced with their minimized values. Typically, the template will contain all or a subset of Goal's variables.

min_max(+Goal, ?C, +Low, +High, +Percent)
minimize(+Goal, ?Term, +Low, +High, +Percent)
Similar to min_max/2 and minimize/2, however the branch and bound method starts with the assumption that the value to be minimised is less than or equal to High. Moreover, as soon as a solution is found whose minimised value is less than Low, this solution is returned. Solutions within the range of Percent % are considered equivalent and so the search for next better solution starts with a minimised value Percent % less than the previously found one. Low, High and Percent must be integers.

min_max(+Goal, ?C, +Low, +High, +Percent, +Timeout)
minimize(+Goal, ?Term, +Low, +High, +Percent, +Timeout)
Similar to min_max/5 and minimize/5, but after Timeout seconds the search is aborted and the best solution found so far is returned.

min_max(+Goal, ?Template, ?Solution, ?C, +Low, +High, +Percent, +Timeout)
minimize(+Goal, ?Template, ?Solution, ?Term, +Low, +High, +Percent, +Timeout)
The most general variants of the above, with all the optinal parameters.


next up previous index
Next: Arithmetic Constraint Predicates Up: The Finite Domains Library Previous: Terminology   Index
Warwick Harvey
2004-08-07