5.223. lex_chain_greater
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Usual name
- Type
- Argument
- Restrictions
- Purpose
For each pair of consecutive vectors and of the collection we have that is lexicographically strictly greater than . Given two vectors, and of components, and , is lexicographically strictly greater than if and only if or and is lexicographically strictly greater than .
- Example
-
The constraint holds since:
The first vector of the collection is lexicographically strictly greater than the second vector of the collection.
The second vector of the collection is lexicographically strictly greater than the third vector of the collection.
- Typical
- Arg. properties
Contractible wrt. .
Suffix-extensible wrt. (add items at same position).
- Usage
This constraint was motivated for breaking symmetry: more precisely when one wants to lexicographically order the consecutive columns of a matrix of decision variables. A further motivation is that using a set of lexicographic ordering constraints between two vectors does usually not allows to come up with a complete pruning.
- Algorithm
A filtering algorithm achieving arc-consistency for a chain of lexicographical ordering constraints is presented inΒ [BeldiceanuCarlsson02c].
- See also
common keyword: , , , Β (lexicographic order).
implies: , .
- Keywords
application area: floor planning problem.
characteristic of a constraint: vector.
constraint type: decomposition, order constraint, system of constraints.
heuristics: heuristics and lexicographical ordering.
modelling: degree of diversity of a set of solutions.
modelling exercises: degree of diversity of a set of solutions.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.223.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the arcs of the final graph are stressed in bold. The constraint holds since all the arc constraints of the initial graph are satisfied.
Figure 5.223.1. Initial and final graph of the constraint
(a) (b) - Signature
Since we use the arc generator on the collection the number of arcs of the initial graph is equal to . For this reason we can rewrite to and simplify to .