5.189. lex_chain_less

Origin

[BeldiceanuCarlsson02c]

Constraint

lex_chain_less​(VECTORS)​

Usual name

lex_chain

Type(s)

VECTOR

collection​(var−dvar)​

Argument(s)

VECTORS

collection​(vec−VECTOR)​

Restriction(s)

required​(VECTOR,​var)​

required​(VECTORS,​vec)​

same_size​(VECTORS,​vec)​

Purpose

For each pair of consecutive vectors VECTOR_i and VECTOR_i+1 of the VECTORS collection we have that VECTOR_i is lexicographically strictly less than VECTOR_i+1. Given two vectors, X and Y of n components, 〈X₀,​...,​X_n−1〉 and 〈Y₀,​...,​Y_n−1〉, X is lexicographically strictly less than Y if and only if X₀​<Y₀ or X₀=Y₀ and 〈X₁,​...,​X_n−1〉 is lexicographically strictly less than 〈Y₁,​...,​Y_n−1〉.

Example

( 〈 vec−〈5,​2,​3,​9〉,​ vec−〈5,​2,​6,​2〉,​ vec−〈5,​2,​6,​3〉 〉 )

The lex_chain_less constraint holds since:

• The first vector 〈5,​2,​3,​9〉 of the VECTORS collection is lexicographically strictly less than the second vector 〈5,​2,​6,​2〉 of the VECTORS collection.

• The second vector 〈5,​2,​6,​2〉 of the VECTORS collection is lexicographically strictly less than the third vector 〈5,​2,​6,​3〉 of the VECTORS 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 diffn or geost and within their corresponding necessary condition like the cumulative constraint are shown in [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].

Systems

lex_chain in SICStus.

See also

lex_between, lex_chain_lesseq, lex_less, lex_lesseq, lex_greater, lex_greatereq, diffn, geost, cumulative.

Key words

application area: floor planning problem.

characteristic of a constraint: vector.

constraint type: decomposition, order constraint.

filtering: arc-consistency.

heuristics: heuristics and lexicographical ordering.

modelling: degree of diversity of a set of solutions.

symmetry: symmetry, matrix symmetry, lexicographic order.

Arc input(s)

VECTORS

Arc generator

PATH↦collection​(vectors1,​vectors2)​

Arc arity

2

Arc constraint(s)

lex_less​(vectors1.vec,​vectors2.vec)​

Graph property(ies)

NARC=|VECTORS|−1

---

Graph model

Parts (A) and (B) of Figure 5.189.1 respectively show the initial and final graph associated with the Example slot. Since we use the NARC graph property, the arcs of the final graph are stressed in bold. The lex_chain_less constraint holds since all the arc constraints of the initial graph are satisfied.

Figure 5.189.1. Initial and final graph of the lex_chain_less constraint

(a)	(b)

Signature

Since we use the PATH arc generator on the VECTORS collection the number of arcs of the initial graph is equal to |VECTORS|−1. For this reason we can rewrite NARC=|VECTORS|−1 to NARC≥|VECTORS|−1 and simplify NARC to NARC.