5.229. lex_greater
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
CHIP
- Constraint
- Synonyms
, , , , .
- Arguments
- Restrictions
- Purpose
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 is lexicographically strictly greater than .
- Typical
- Symmetries
- Arg. properties
Suffix-extensible wrt. and (add items at same position).
- Remark
A multiset ordering constraint and its corresponding filtering algorithm are described inย [FriHniKizMigWal03].
- Algorithm
The first filtering algorithm maintaining arc-consistency for this constraint was presented inย [FrischHnichKiziltanMiguelWalsh02]. A second filtering algorithm maintaining arc-consistency and detecting entailment in a more eager way, was given inย [BeldiceanuCarlsson02b]. This second algorithm was derived from a deterministic finite automata. A third filtering algorithm extending the algorithm presented inย [FrischHnichKiziltanMiguelWalsh02] detecting entailment is given in the PhD thesis of Z.ย Kฤฑzฤฑltanย [Kiziltan04]. The previous thesisย [Kiziltan04] presents also a filtering algorithm handling the fact that a given variable has more than one occurrence. Finally, T.ย Frรผhwirth shows how to encode lexicographic ordering constraints within the context of CHRย [Fruhwirth98] inย [Fruhwirth06].
- Reformulation
The following reformulations in term of arithmetic and/or logical expressions exist for enforcing the lexicographically strictly greater than constraint. The first one converts and into numbers and post an inequality constraint. It assumes all components of and to be within :
Since the previous reformulation can only be used with small values of and , W.ย Harvey came up with the following alternative model that maintains arc-consistency:
Finally, the lexicographically strictly greater than constraint can be expressed as a conjunction or a disjunction of constraints:
When used separately, the two previous logical decompositions do not maintain arc-consistency.
- Systems
lex in Choco, rel in Gecode, lex_greater in MiniZinc, lex_chain in SICStus.
- Used in
- See also
common keyword: , , , , ย (lexicographic order).
implies: , .
- Keywords
characteristic of a constraint: vector, automaton, automaton without counters, reified automaton constraint, derived collection.
constraint network structure: Berge-acyclic constraint network.
constraint type: order constraint.
filtering: duplicated variables, arc-consistency.
heuristics: heuristics and lexicographical ordering.
symmetry: symmetry, matrix symmetry, lexicographic order, multiset ordering.
- Derived Collections
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
Partsย (A) andย (B) of Figureย 5.229.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property we show the following information on the final graph:
The vertices, which respectively correspond to the start and the end of the required path, are stressed in bold.
The arcs on the required path are also stressed in bold.
Figure 5.229.1. Initial and final graph of the constraint
(a) (b) The vertices of the initial graph are generated in the following way:
We create a vertex for each pair of components that both have the same index .
We create an additional dummy vertex called .
The arcs of the initial graph are generated in the following way:
We create an arc between and . We associate to this arc the arc constraint .
We create an arc between and . We associate to this arc the arc constraint .
The constraint holds when there exist a path from to . This path can be interpreted as a sequence of equality constraints on the prefix of both vectors, immediately followed by a greater than constraint.
- Signature
Since the maximum value returned by the graph property is equal to 1 we can rewrite to . Therefore we simplify to .
- Automaton
Figureย 5.229.2 depicts the automaton associated with the constraint. Let and respectively be the attributes of the items of the and the collections. To each pair corresponds a signature variable as well as the following signature constraint: .
Figure 5.229.2. Automaton of the constraint
Figure 5.229.3. Hypergraph of the reformulation corresponding to the automaton of the constraint