5.188. lex_between

Origin

[BeldiceanuCarlsson02c]

Constraint

lex_between​(LOWER_BOUND,​VECTOR,​UPPER_BOUND)​

Synonym(s)

between.

Argument(s)

LOWER_BOUND	collection​(var−int)​
VECTOR	collection​(var−dvar)​
UPPER_BOUND	collection​(var−int)​

Restriction(s)

required​(LOWER_BOUND,​var)​

required​(VECTOR,​var)​

required​(UPPER_BOUND,​var)​

|LOWER_BOUND|=|VECTOR|

|UPPER_BOUND|=|VECTOR|

lex_lesseq​(LOWER_BOUND,​VECTOR)​

lex_lesseq​(VECTOR,​UPPER_BOUND)​

Purpose

The vector VECTOR is lexicographically greater than or equal to the fixed vector LOWER_BOUND and lexicographically smaller than or equal to the fixed vector UPPER_BOUND.

Example

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

The lex_between constraint holds since:

• The vector VECTOR=〈5,​2,​6,​2〉 is greater than or equal to the vector LOWER_BOUND=〈5,​2,​3,​9〉.

• The vector VECTOR=〈5,​2,​6,​2〉 is less than or equal to the vector UPPER_BOUND=〈5,​2,​6,​3〉.

Usage

This constraint does usually not occur explicitly in practice. However it shows up indirectly in the context of the lex_chain_less and the lex_chain_lesseq constraints: in order to have a complete filtering algorithm for the lex_chain_less and the lex_chain_lesseq constraints one has to come up with a complete filtering algorithm for the lex_between constraint. The reason is that the lex_chain_less as well as the lex_chain_lesseq constraints both compute feasible lower and upper bounds for each vector they mention. Therefore one ends up with a lex_between constraint for each vector of the lex_chain_less and lex_chain_lesseq constraints.

Algorithm

[BeldiceanuCarlsson02c].

Reformulation

The lex_between​(LOWER_BOUND,​VECTORS,​UPPER_BOUND)​ constraint can be expressed as the conjunction lex_lesseq​(LOWER_BOUND,​VECTORS)​ ∧ lex_lesseq​(VECTORS,​UPPER_BOUND)​.

Systems

lex_chain in SICStus.

See also

lex_less, lex_lesseq, lex_greater, lex_greatereq, lex_chain_less, lex_chain_lesseq.

Key words

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

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

symmetry: symmetry, lexicographic order.

Automaton

Figure 5.188.1 depicts the automaton associated with the lex_between constraint. Let L_i, V_i and U_i respectively be the var attributes of the i^th items of the LOWER_BOUND, the VECTOR and the UPPER_BOUND collections. To each triple ​(L_i,​V_i,​U_i)​ corresponds a signature variable S_i as well as the following signature constraint:

      ​(L_i​<V_i)​∧​(V_i​<U_i)​⇔S_i=0 ∧

      ​(L_i​<V_i)​∧​(V_i=U_i)​⇔S_i=1 ∧

      ​(L_i​<V_i)​∧​(V_i>​U_i)​⇔S_i=2 ∧

      ​(L_i=V_i)​∧​(V_i​<U_i)​⇔S_i=3 ∧

      ​(L_i=V_i)​∧​(V_i=U_i)​⇔S_i=4 ∧

      ​(L_i=V_i)​∧​(V_i>​U_i)​⇔S_i=5 ∧

      ​(L_i>​V_i)​∧​(V_i​<U_i)​⇔S_i=6 ∧

      ​(L_i>​V_i)​∧​(V_i=U_i)​⇔S_i=7 ∧

      ​(L_i>​V_i)​∧​(V_i>​U_i)​⇔S_i=8.

Figure 5.188.1. Automaton of the lex_between constraint

Figure 5.188.2. Hypergraph of the reformulation corresponding to the automaton of the lex_between constraint