5.194. lex_chain_lesseq

DESCRIPTIONLINKSGRAPH
Origin

[BeldiceanuCarlsson02c]

Constraint

πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš(πš…π™΄π™²πšƒπ™Ύπšπš‚)

Usual name

πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Argument
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

For each pair of consecutive vectors πš…π™΄π™²πšƒπ™Ύπš i and πš…π™΄π™²πšƒπ™Ύπš i+1 of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection we have that πš…π™΄π™²πšƒπ™Ύπš i is lexicographically less than or equal to πš…π™΄π™²πšƒπ™Ύπš i+1 . Given two vectors, X β†’ and Y β†’ of n components, 〈X 0 ,...,X n-1 βŒͺ and 〈Y 0 ,...,Y n-1 βŒͺ, X β†’ is lexicographically less than or equal to Y β†’ if and only if n=0 or X 0 <Y 0 or X 0 =Y 0 and 〈X 1 ,...,X n-1 βŒͺ is lexicographically less than or equal to 〈Y 1 ,...,Y n-1 βŒͺ.

Example
𝚟𝚎𝚌-5,2,3,9,𝚟𝚎𝚌-5,2,6,2,𝚟𝚎𝚌-5,2,6,2

The πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraint holds since:

  • The first vector 〈5,2,3,9βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection is lexicographically less than or equal to the second vector 〈5,2,6,2βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection.

  • The second vector 〈5,2,6,2βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection is lexicographically less than or equal to the third vector 〈5,2,6,2βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection.

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].

Six different ways of integrating a chain of lexicographical ordering constraints within non -overlapping constraints like πšπš’πšπšπš— or 𝚐𝚎𝚘𝚜𝚝 and within their corresponding necessary condition like the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint are shown inΒ [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

lexChainEq in Choco, lex_chain in SICStus.

See also

common keyword: πšŠπš•πš•πš™πšŽπš›πš–Β (lexicographic order), 𝚐𝚎𝚘𝚜𝚝 (symmetry, lexicographic ordering on the origins of πšπšŠπšœπš”πšœ, πš›πšŽπšŒπšπšŠπš—πšπš•πšŽπšœ, ...), πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš—, πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›, πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πš•πšŽπš‘_πš•πšŽπšœπšœΒ (lexicographic order).

implied by: πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœΒ (non-strict order implied by strict order),

πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (π™½πš…π™΄π™² of constraint πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš› removed),

πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (π™½πš…π™΄π™² of constraint πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› removed),

πš˜πš›πšπšŽπš›πšŽπš_πš—πšŸπšŽπšŒπšπš˜πš›Β (π™½πš…π™΄π™² of constraint πš˜πš›πšπšŽπš›πšŽπš_πš—πšŸπšŽπšŒπšπš˜πš› removed).

part of system of constraints: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

related: πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ, πšπš’πšπšπš—Β (lexicographic ordering on the origins of πšπšŠπšœπš”πšœ, πš›πšŽπšŒπšπšŠπš—πšπš•πšŽπšœ, ...).

system of constraints: πš•πšŽπš‘2.

used in graph description: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

Keywords

characteristic of a constraint: vector.

constraint type: system of constraints, decomposition, order constraint.

filtering: arc-consistency.

heuristics: heuristics and lexicographical ordering.

symmetry: symmetry, matrix symmetry, lexicographic order.

Arc input(s)

πš…π™΄π™²πšƒπ™Ύπšπš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŽπšŒπšπš˜πš›πšœ1,πšŸπšŽπšŒπšπš˜πš›πšœ2)

Arc arity
Arc constraint(s)
πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(πšŸπšŽπšŒπšπš˜πš›πšœ1.𝚟𝚎𝚌,πšŸπšŽπšŒπšπš˜πš›πšœ2.𝚟𝚎𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.194.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.194.1. Initial and final graph of the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraint
ctrs/lex_chain_lesseqActrs/lex_chain_lesseqB
(a) (b)
Signature

Since we use the 𝑃𝐴𝑇𝐻 arc generator on the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection the number of arcs of the initial graph is equal to |πš…π™΄π™²πšƒπ™Ύπšπš‚|-1. For this reason we can rewrite 𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1 to 𝐍𝐀𝐑𝐂β‰₯|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.