5.190. lex2

DESCRIPTIONLINKS
Origin

[FlenerFrischHnichKiziltanMiguelPearsonWalsh02]

Constraint

πš•πšŽπš‘2(π™Όπ™°πšƒπšπ™Έπš‡)

Synonyms

πšπš˜πšžπš‹πš•πšŽ_πš•πšŽπš‘, πš›πš˜πš _πšŠπš—πš_πšŒπš˜πš•πšžπš–πš—_πš•πšŽπš‘.

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

Given a matrix of domain variables, enforces that both adjacent rows, and adjacent columns are lexicographically ordered (adjacent rows and adjacent columns can be equal).

Example
𝚟𝚎𝚌-2,2,3,𝚟𝚎𝚌-2,3,1

The πš•πšŽπš‘2 constraint holds since:

  • The first row 〈2,2,3βŒͺ is lexicographically less than or equal to the second row 〈2,3,1βŒͺ.

  • The first column 〈2,2βŒͺ is lexicographically less than or equal to the second column 〈2,3βŒͺ.

  • The second column 〈2,3βŒͺ is lexicographically less than or equal to the third column 〈3,1βŒͺ.

Symmetry

One and the same constant can be added to the πšŸπšŠπš› attribute of all items of π™Όπ™°πšƒπšπ™Έπš‡.𝚟𝚎𝚌.

Usage

A symmetry-breaking constraint.

Remark

The idea of this symmetry-breaking constraint can already be found in the following articles of A.Β LubiwΒ [Lubiw85], [Lubiw87].

In block designs you sometimes want repeated blocks, so using the non-strict order would be required in this case.

Reformulation

The πš•πšŽπš‘2 constraint can be expressed as a conjunction of two πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints: A first πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraint on the π™Όπ™°πšƒπšπ™Έπš‡ argument and a second πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraint on the transpose of the π™Όπ™°πšƒπšπ™Έπš‡ argument.

See also

common keyword: πšŠπš•πš•πš™πšŽπš›πš–, πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπššΒ (matrix symmetry,lexicographic order).

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

part of system of constraints: πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš.

Keywords

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

modelling: matrix, matrix model.

symmetry: symmetry, matrix symmetry, lexicographic order.