Global Constraint Catalog: Clex_chain

5.226. lex_chain_lesseq

DESCRIPTION

LINKS

GRAPH

Origin

[BeldiceanuCarlsson02c]

Constraint

$𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚 (𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$

Usual name

$𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗$

Type

𝚅𝙴𝙲𝚃𝙾𝚁

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Argument

𝚅𝙴𝙲𝚃𝙾𝚁𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

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, $\vec{X}$ and $\vec{Y}$ of $n$ components, $〈 X_{0}, \dots, X_{n - 1} 〉$ and $〈 Y_{0}, \dots, Y_{n - 1} 〉$ , $\vec{X}$ is lexicographically less than or equal to $\vec{Y}$ if and only if $n = 0$ or $X_{0} < Y_{0}$ or $X_{0} = Y_{0}$ and $〈 X_{1}, \dots, X_{n - 1} 〉$ is lexicographically less than or equal to $〈 Y_{1}, \dots, 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.

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 | > 1

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

Arg. properties

Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ .
Suffix-contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ (remove items from 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].

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: $𝚕𝚎𝚡 2$ (columns lex ordering imposed by constraint $𝚕𝚎𝚡 2$ removed), $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ (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

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2)

Arc arity

Arc constraint(s)

𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚

(𝚟𝚎𝚌𝚝𝚘𝚛𝚜 1 . 𝚟𝚎𝚌, 𝚟𝚎𝚌𝚝𝚘𝚛𝚜 2 . 𝚟𝚎𝚌)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1

Graph model

Parts (A) and (B) of Figure 5.226.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.226.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 $| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1$ . For this reason we can rewrite $𝐍𝐀𝐑𝐂 = | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1$ to $𝐍𝐀𝐑𝐂 \geq | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | - 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.226. lex_chain_lesseq

Figure 5.226.1. Initial and final graph of the 𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚 constraint

Figure 5.226.1. Initial and final graph of the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜𝚎𝚚$ constraint