5.193. lex_chain_less

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 strictly less than πš…π™΄π™²πšƒπ™Ύπš 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 strictly less than Y β†’ if and only if X 0 <Y 0 or X 0 =Y 0 and 〈X 1 ,...,X n-1 βŒͺ is lexicographically strictly less than 〈Y 1 ,...,Y n-1 βŒͺ.

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

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

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

  • The second vector 〈5,2,6,2βŒͺ of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection is lexicographically strictly less than the third vector 〈5,2,6,3βŒͺ 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

lexChain in Choco, lex_chain in SICStus.

See also

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

implied by: πšœπšπš›πš’πšŒπš_πš•πšŽπš‘2.

implies: πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš.

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

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

system of constraints: πšœπšπš›πš’πšŒπš_πš•πšŽπš‘2.

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

Keywords

application area: floor planning problem.

characteristic of a constraint: vector.

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

filtering: arc-consistency.

heuristics: heuristics and lexicographical ordering.

modelling: degree of diversity of a set of solutions.

modelling exercises: degree of diversity of a set of solutions.

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.193.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.193.1. Initial and final graph of the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ constraint
ctrs/lex_chain_lessActrs/lex_chain_lessB
(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 𝐍𝐀𝐑𝐂 Β―.