Did you know ... | Search Documentation: |

Global constraints |

- Home
- DOWNLOAD
- DOCUMENTATION
- TUTORIALS
- Beginner▶
- Advanced▶
- Web applications▶
- Semantic web▶
- Graphics▶
- Machine learning▶
- External collections▶
- For packagers▶

- COMMUNITY
- USERS
- WIKI

A *global constraint* expresses a relation that involves many
variables at once. The most frequently used global constraints of this
library are the combinatorial constraints all_distinct/1,
global_cardinality/2
and cumulative/2.

**all_distinct**(`+Vars`)- True iff
`Vars`are pairwise distinct. For example, all_distinct/1 can detect that not all variables can assume distinct values given the following domains:?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]), all_distinct(Vs). false.

**all_different**(`+Vars`)- Like all_distinct/1, but with weaker propagation. Consider using all_distinct/1 instead, since all_distinct/1 is typically acceptably efficient and propagates much more strongly.
**sum**(`+Vars, +Rel, ?Expr`)- The sum of elements of the list
`Vars`is in relation`Rel`to`Expr`.`Rel`is one of #=, #`\`

=, #`<`, #`>`,`#=<`

or #`>`=. For example:?- [A,B,C] ins 0..sup, sum([A,B,C], #=, 100). A in 0..100, A+B+C#=100, B in 0..100, C in 0..100.

**scalar_product**(`+Cs, +Vs, +Rel, ?Expr`)- True iff the scalar product of
`Cs`and`Vs`is in relation`Rel`to`Expr`.`Cs`is a list of integers,`Vs`is a list of variables and integers.`Rel`is #=, #`\`

=, #`<`, #`>`,`#=<`

or #`>`=. **lex_chain**(`+Lists`)`Lists`are lexicographically non-decreasing.**tuples_in**(`+Tuples, +Relation`)- True iff all
`Tuples`are elements of`Relation`. Each element of the list`Tuples`is a list of integers or finite domain variables.`Relation`is a list of lists of integers. Arbitrary finite relations, such as compatibility tables, can be modeled in this way. For example, if 1 is compatible with 2 and 5, and 4 is compatible with 0 and 3:?- tuples_in([[X,Y]], [[1,2],[1,5],[4,0],[4,3]]), X = 4. X = 4, Y in 0\/3.

As another example, consider a train schedule represented as a list of quadruples, denoting departure and arrival places and times for each train. In the following program, Ps is a feasible journey of length 3 from A to D via trains that are part of the given schedule.

trains([[1,2,0,1], [2,3,4,5], [2,3,0,1], [3,4,5,6], [3,4,2,3], [3,4,8,9]]). threepath(A, D, Ps) :- Ps = [[A,B,_T0,T1],[B,C,T2,T3],[C,D,T4,_T5]], T2 #> T1, T4 #> T3, trains(Ts), tuples_in(Ps, Ts).

In this example, the unique solution is found without labeling:

?- threepath(1, 4, Ps). Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].

**serialized**(`+Starts, +Durations`)- Describes a set of non-overlapping tasks.
`Starts`= [S_1,...,S_n], is a list of variables or integers,`Durations`= [D_1,...,D_n] is a list of non-negative integers. Constrains`Starts`and`Durations`to denote a set of non-overlapping tasks, i.e.: S_i + D_i`=<`

S_j or S_j + D_j`=<`

S_i for all 1`=<`

i`<`j`=<`

n. Example:?- length(Vs, 3), Vs ins 0..3, serialized(Vs, [1,2,3]), label(Vs). Vs = [0, 1, 3] ; Vs = [2, 0, 3] ; false.

- See also
- Dorndorf et al. 2000, "Constraint Propagation Techniques for the Disjunctive Scheduling Problem"

**element**(`?N, +Vs, ?V`)- The
`N`-th element of the list of finite domain variables`Vs`is`V`. Analogous to nth1/3. **global_cardinality**(`+Vs, +Pairs`)- Global Cardinality constraint. Equivalent to
`global_cardinality(Vs, Pairs, [])`

. See global_cardinality/3.Example:

?- Vs = [_,_,_], global_cardinality(Vs, [1-2,3-_]), label(Vs). Vs = [1, 1, 3] ; Vs = [1, 3, 1] ; Vs = [3, 1, 1].

**global_cardinality**(`+Vs, +Pairs, +Options`)- Global Cardinality constraint.
`Vs`is a list of finite domain variables,`Pairs`is a list of Key-Num pairs, where Key is an integer and Num is a finite domain variable. The constraint holds iff each V in`Vs`is equal to some key, and for each Key-Num pair in`Pairs`, the number of occurrences of Key in`Vs`is Num.`Options`is a list of options. Supported options are:**consistency**(`value`)- A weaker form of consistency is used.
**cost**(`Cost, Matrix`)`Matrix`is a list of rows, one for each variable, in the order they occur in`Vs`. Each of these rows is a list of integers, one for each key, in the order these keys occur in`Pairs`. When variable v_i is assigned the value of key k_j, then the associated cost is`Matrix`_{ij}.`Cost`is the sum of all costs.

**circuit**(`+Vs`)- True iff the list
`Vs`of finite domain variables induces a Hamiltonian circuit. The k-th element of`Vs`denotes the successor of node k. Node indexing starts with 1. Examples:?- length(Vs, _), circuit(Vs), label(Vs). Vs = [] ; Vs = [1] ; Vs = [2, 1] ; Vs = [2, 3, 1] ; Vs = [3, 1, 2] ; Vs = [2, 3, 4, 1] .

**cumulative**(`+Tasks`)- Equivalent to
`cumulative(Tasks, [limit(1)])`

. See cumulative/2. **cumulative**(`+Tasks, +Options`)- Schedule with a limited resource.
`Tasks`is a list of tasks, each of the form`task(S_i, D_i, E_i, C_i, T_i)`

. S_i denotes the start time, D_i the positive duration, E_i the end time, C_i the non-negative resource consumption, and T_i the task identifier. Each of these arguments must be a finite domain variable with bounded domain, or an integer. The constraint holds iff at each time slot during the start and end of each task, the total resource consumption of all tasks running at that time does not exceed the global resource limit.`Options`is a list of options. Currently, the only supported option is:**limit**(`L`)- The integer
`L`is the global resource limit. Default is 1.

For example, given the following predicate that relates three tasks of durations 2 and 3 to a list containing their starting times:

tasks_starts(Tasks, [S1,S2,S3]) :- Tasks = [task(S1,3,_,1,_), task(S2,2,_,1,_), task(S3,2,_,1,_)].

We can use cumulative/2 as follows, and obtain a schedule:

?- tasks_starts(Tasks, Starts), Starts ins 0..10, cumulative(Tasks, [limit(2)]), label(Starts). Tasks = [task(0, 3, 3, 1, _G36), task(0, 2, 2, 1, _G45), ...], Starts = [0, 0, 2] .

**disjoint2**(`+Rectangles`)- True iff
`Rectangles`are not overlapping.`Rectangles`is a list of terms of the form F(X_i, W_i, Y_i, H_i), where F is any functor, and the arguments are finite domain variables or integers that denote, respectively, the X coordinate, width, Y coordinate and height of each rectangle. **automaton**(`+Vs, +Nodes, +Arcs`)- Describes a list of finite domain variables with a finite automaton.
Equivalent to
`automaton(Vs, _, Vs, Nodes, Arcs, [], [], _)`

, a common use case of automaton/8. In the following example, a list of binary finite domain variables is constrained to contain at least two consecutive ones:two_consecutive_ones(Vs) :- automaton(Vs, [source(a),sink(c)], [arc(a,0,a), arc(a,1,b), arc(b,0,a), arc(b,1,c), arc(c,0,c), arc(c,1,c)]).

Example query:

?- length(Vs, 3), two_consecutive_ones(Vs), label(Vs). Vs = [0, 1, 1] ; Vs = [1, 1, 0] ; Vs = [1, 1, 1].

**automaton**(`+Sequence, ?Template, +Signature, +Nodes, +Arcs, +Counters, +Initials, ?Finals`)- Describes a list of finite domain variables with a finite automaton.
True iff the finite automaton induced by
`Nodes`and`Arcs`(extended with`Counters`) accepts`Signature`.`Sequence`is a list of terms, all of the same shape. Additional constraints must link`Sequence`to`Signature`, if necessary.`Nodes`is a list of`source(Node)`

and`sink(Node)`

terms.`Arcs`is a list of`arc(Node,Integer,Node)`

and`arc(Node,Integer,Node,Exprs)`

terms that denote the automaton's transitions. Each node is represented by an arbitrary term. Transitions that are not mentioned go to an implicit failure node.`Exprs`is a list of arithmetic expressions, of the same length as`Counters`. In each expression, variables occurring in`Counters`symbolically refer to previous counter values, and variables occurring in`Template`refer to the current element of`Sequence`. When a transition containing arithmetic expressions is taken, each counter is updated according to the result of the corresponding expression. When a transition without arithmetic expressions is taken, all counters remain unchanged.`Counters`is a list of variables.`Initials`is a list of finite domain variables or integers denoting, in the same order, the initial value of each counter. These values are related to`Finals`according to the arithmetic expressions of the taken transitions.The following example is taken from Beldiceanu, Carlsson, Debruyne and Petit: "Reformulation of Global Constraints Based on Constraints Checkers", Constraints 10(4), pp 339-362 (2005). It relates a sequence of integers and finite domain variables to its number of inflexions, which are switches between strictly ascending and strictly descending subsequences:

sequence_inflexions(Vs, N) :- variables_signature(Vs, Sigs), automaton(Sigs, _, Sigs, [source(s),sink(i),sink(j),sink(s)], [arc(s,0,s), arc(s,1,j), arc(s,2,i), arc(i,0,i), arc(i,1,j,[C+1]), arc(i,2,i), arc(j,0,j), arc(j,1,j), arc(j,2,i,[C+1])], [C], [0], [N]). variables_signature([], []). variables_signature([V|Vs], Sigs) :- variables_signature_(Vs, V, Sigs). variables_signature_([], _, []). variables_signature_([V|Vs], Prev, [S|Sigs]) :- V #= Prev #<==> S #= 0, Prev #< V #<==> S #= 1, Prev #> V #<==> S #= 2, variables_signature_(Vs, V, Sigs).

Example queries:

?- sequence_inflexions([1,2,3,3,2,1,3,0], N). N = 3. ?- length(Ls, 5), Ls ins 0..1, sequence_inflexions(Ls, 3), label(Ls). Ls = [0, 1, 0, 1, 0] ; Ls = [1, 0, 1, 0, 1].

**chain**(`+Zs, +Relation`)`Zs`form a chain with respect to`Relation`.`Zs`is a list of finite domain variables that are a chain with respect to the partial order`Relation`, in the order they appear in the list.`Relation`must be #=, #=`<`, #`>`=,`#<`

or #`>`. For example:?- chain([X,Y,Z], #>=). X#>=Y, Y#>=Z.

Tag confusing pages with **doc-needs-help**|Tags are associated to your profile if you are logged in

Tags: