5.193. lex_chain_less

Origin
Constraint

$\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }\right)$

Usual name

$\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi }$

Type
 $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Argument
 $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi £\pi }$$\left(\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi },\mathrm{\pi \pi \pi }\right)$
Purpose

For each pair of consecutive vectors ${\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }}_{i}$ and ${\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }}_{i+1}$ of the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ collection we have that ${\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }}_{i}$ is lexicographically strictly less than ${\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi }}_{i+1}$. Given two vectors, $\stackrel{\beta }{X}$ and $\stackrel{\beta }{Y}$ of $n$ components, $\beta ©{X}_{0},...,{X}_{n-1}\beta ͺ$ and $\beta ©{Y}_{0},...,{Y}_{n-1}\beta ͺ$, $\stackrel{\beta }{X}$ is lexicographically strictly less than $\stackrel{\beta }{Y}$ if and only if ${X}_{0}<{Y}_{0}$ or ${X}_{0}={Y}_{0}$ and $\beta ©{X}_{1},...,{X}_{n-1}\beta ͺ$ is lexicographically strictly less than $\beta ©{Y}_{1},...,{Y}_{n-1}\beta ͺ$.

Example
$\left(\begin{array}{c}β©\begin{array}{c}\mathrm{\pi \pi \pi }-β©5,2,3,9βͺ,\hfill \\ \mathrm{\pi \pi \pi }-β©5,2,6,2βͺ,\hfill \\ \mathrm{\pi \pi \pi }-β©5,2,6,3βͺ\hfill \end{array}βͺ\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint holds since:

• The first vector $\beta ©5,2,3,9\beta ͺ$ of the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ collection is lexicographically strictly less than the second vector $\beta ©5,2,6,2\beta ͺ$ of the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ collection.

• The second vector $\beta ©5,2,6,2\beta ͺ$ of the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ collection is lexicographically strictly less than the third vector $\beta ©5,2,6,3\beta ͺ$ of the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ 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 $\mathrm{\pi \pi \pi \pi \pi }$ or $\mathrm{\pi \pi \pi \pi \pi }$ and within their corresponding necessary condition like the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint are shown inΒ [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

common keyword: $\mathrm{\pi \pi \pi \pi \pi }$Β (symmetry, lexicographic ordering on the origins of $\mathrm{\pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $...$), , $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi \pi }$Β (lexicographic order).

related: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }$Β (lexicographic ordering on the origins of $\mathrm{\pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $...$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$

Arc generator
$\mathrm{\pi \pi ΄\pi \pi »}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=|\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }|-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 $\mathrm{\pi \pi \pi \pi }$ graph property, the arcs of the final graph are stressed in bold. The $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint holds since all the arc constraints of the initial graph are satisfied.

Signature

Since we use the $\mathrm{\pi \pi ΄\pi \pi »}$ arc generator on the $\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }$ collection the number of arcs of the initial graph is equal to $|\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }|-1$. For this reason we can rewrite $\mathrm{\pi \pi \pi \pi }=|\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }|-1$ to $\mathrm{\pi \pi \pi \pi }\beta ₯|\mathrm{\pi  \pi ΄\pi ²\pi \pi Ύ\pi \pi }|-1$ and simplify $\underset{Μ²}{\stackrel{Β―}{\mathrm{\pi \pi \pi \pi }}}$ to $\stackrel{Β―}{\mathrm{\pi \pi \pi \pi }}$.