5.192. lex_between

DESCRIPTIONLINKSAUTOMATON
Origin

[BeldiceanuCarlsson02c]

Constraint

πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš—(π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³,πš…π™΄π™²πšƒπ™Ύπš,πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³)

Synonym

πš‹πšŽπšπš πšŽπšŽπš—.

Arguments
π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πš’πš—πš)
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³,πšŸπšŠπš›)
|π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³|=|πš…π™΄π™²πšƒπ™Ύπš|
|πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³|=|πš…π™΄π™²πšƒπ™Ύπš|
πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³,πš…π™΄π™²πšƒπ™Ύπš)
πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(πš…π™΄π™²πšƒπ™Ύπš,πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³)
Purpose

The vector πš…π™΄π™²πšƒπ™Ύπš is lexicographically greater than or equal to the fixed vector π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³ and lexicographically smaller than or equal to the fixed vector πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³.

Example
5,2,3,9,5,2,6,2,5,2,6,3

The πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint holds since:

  • The vector πš…π™΄π™²πšƒπ™Ύπš=〈5,2,6,2βŒͺ is greater than or equal to the vector π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³=〈5,2,3,9βŒͺ.

  • The vector πš…π™΄π™²πšƒπ™Ύπš=〈5,2,6,2βŒͺ is less than or equal to the vector πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³=〈5,2,6,3βŒͺ.

Symmetries
  • π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³.πšŸπšŠπš› can be decreased.

  • πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³.πšŸπšŠπš› can be increased.

Usage

This constraint does usually not occur explicitly in practice. However it shows up indirectly in the context of the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ and the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints: in order to have a complete filtering algorithm for the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ and the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints one has to come up with a complete filtering algorithm for the πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint. The reason is that the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ as well as the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints both compute feasible lower and upper bounds for each vector they mention. Therefore one ends up with a πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint for each vector of the πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ and πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints.

Algorithm

[BeldiceanuCarlsson02c].

Reformulation

The πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš—(π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³,πš…π™΄π™²πšƒπ™Ύπšπš‚,πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³) constraint can be expressed as the conjunction πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³,πš…π™΄π™²πšƒπ™Ύπšπš‚) ∧ πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(πš…π™΄π™²πšƒπ™Ύπšπš‚,πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³).

Systems

lexChainEq in Choco, lex_chain in SICStus.

See also

common keyword: πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ, πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš, πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›, πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πš•πšŽπš‘_πš•πšŽπšœπšœΒ (lexicographic order).

part of system of constraints: πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

Keywords

characteristic of a constraint: vector, automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint, system of constraints.

filtering: arc-consistency.

symmetry: symmetry, lexicographic order.

Automaton

FigureΒ 5.192.1 depicts the automaton associated with the πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint. Let 𝙻 i , πš… i and πš„ i respectively be the πšŸπšŠπš› attributes of the i th items of the π™»π™Ύπš†π™΄πš_π™±π™Ύπš„π™½π™³, the πš…π™΄π™²πšƒπ™Ύπš and the πš„π™Ώπ™Ώπ™΄πš_π™±π™Ύπš„π™½π™³ collections. To each triple (𝙻 i ,πš… i ,πš„ i ) corresponds a signature variable πš‚ i as well as the following signature constraint:

(𝙻 i <πš… i )∧(πš… i <πš„ i )β‡”πš‚ i =0 ∧

(𝙻 i <πš… i )∧(πš… i =πš„ i )β‡”πš‚ i =1 ∧

(𝙻 i <πš… i )∧(πš… i >πš„ i )β‡”πš‚ i =2 ∧

(𝙻 i =πš… i )∧(πš… i <πš„ i )β‡”πš‚ i =3 ∧

(𝙻 i =πš… i )∧(πš… i =πš„ i )β‡”πš‚ i =4 ∧

(𝙻 i =πš… i )∧(πš… i >πš„ i )β‡”πš‚ i =5 ∧

(𝙻 i >πš… i )∧(πš… i <πš„ i )β‡”πš‚ i =6 ∧

(𝙻 i >πš… i )∧(πš… i =πš„ i )β‡”πš‚ i =7 ∧

(𝙻 i >πš… i )∧(πš… i >πš„ i )β‡”πš‚ i =8.

Figure 5.192.1. Automaton of the πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint
ctrs/lex_between1
Figure 5.192.2. Hypergraph of the reformulation corresponding to the automaton of the πš•πšŽπš‘_πš‹πšŽπšπš πšŽπšŽπš— constraint
ctrs/lex_between2