5.15. allperm

DESCRIPTIONLINKSGRAPH
Origin

[FlenerFrischHnichKiziltanMiguelPearsonWalsh02]

Constraint

πšŠπš•πš•πš™πšŽπš›πš–(π™Όπ™°πšƒπšπ™Έπš‡)

Synonyms

πšŠπš•πš•_πš™πšŽπš›πš–, πšŠπš•πš•_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—πšœ.

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

Given a matrix of domain variables, enforces that the first row is lexicographically less than or equal to all permutations of all other rows.

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

The πšŠπš•πš•πš™πšŽπš›πš– constraint holds since vector 〈1,2,3βŒͺ is lexicographically less than or equal to all the permutations of vector 〈3,1,2βŒͺ (i.e., 〈1,2,3βŒͺ, 〈1,3,2βŒͺ, 〈2,1,3βŒͺ, 〈2,3,1βŒͺ, 〈3,1,2βŒͺ, 〈3,2,1βŒͺ).

Typical
|πš…π™΄π™²πšƒπ™Ύπš|>1
|π™Όπ™°πšƒπšπ™Έπš‡|>1
Symmetry

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

Usage

A symmetry-breaking constraint.

See also

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

part of system of constraints: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–.

used in graph description: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–.

Keywords

characteristic of a constraint: vector.

constraint type: order constraint, system of constraints.

final graph structure: acyclic, bipartite.

modelling: matrix, matrix model.

symmetry: matrix symmetry, symmetry, lexicographic order.

Arc input(s)

π™Όπ™°πšƒπšπ™Έπš‡

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš–πšŠπšπš›πš’πš‘1,πš–πšŠπšπš›πš’πš‘2)

Arc arity
Arc constraint(s)
β€’ πš–πšŠπšπš›πš’πš‘1.πš”πšŽπš’=1
β€’ πš–πšŠπšπš›πš’πš‘2.πš”πšŽπš’>1
β€’ πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš–(πš–πšŠπšπš›πš’πš‘1.𝚟𝚎𝚌,πš–πšŠπšπš›πš’πš‘2.𝚟𝚎𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Όπ™°πšƒπšπ™Έπš‡|-1

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

We generate a graph with an arc constraint πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš_πšŠπš•πš•πš™πšŽπš›πš– between the vertex corresponding to the first item of the π™Όπ™°πšƒπšπ™Έπš‡ collection and the vertices associated with all other items of the π™Όπ™°πšƒπšπ™Έπš‡ collection. This is achieved by specifying that (1)Β an arc should start from the first item (i.e.,Β πš–πšŠπšπš›πš’πš‘1.πš”πšŽπš’=1) and (2)Β an arc should not end on the first item (i.e.,Β πš–πšŠπšπš›πš’πš‘2.πš”πšŽπš’>1). We finally state that all these arcs should belong to the final graph. PartsΒ (A) andΒ (B) of FigureΒ 5.15.1 respectively show the initial and final graph associated with the Example slot.

Figure 5.15.1. Initial and final graph of the πšŠπš•πš•πš™πšŽπš›πš– constraint
ctrs/allpermActrs/allpermB
(a) (b)