5.320. strict_lex2

DESCRIPTIONLINKS
Origin

[FlenerFrischHnichKiziltanMiguelPearsonWalsh02]

Constraint

πšœπšπš›πš’πšŒπš_πš•πšŽπš‘2(π™Όπ™°πšƒπšπ™Έπš‡)

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 cannot be equal).

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

The πšœπšπš›πš’πšŒπš_πš•πšŽπš‘2 constraint holds since:

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

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

  • The second column 〈2,3βŒͺ is lexicographically strictly less than 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.

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: πšŠπš•πš•πš™πšŽπš›πš–, πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπššΒ (lexicographic order).

implies: πš•πšŽπš‘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.