5.154. in_interval_reified

DESCRIPTIONLINKS
Origin

Reified version of πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•.

Constraint

πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•_πš›πšŽπš’πšπš’πšŽπš(πš…π™°πš,π™»π™Ύπš†,πš„π™Ώ,𝙱)

Synonyms

πšπš˜πš–_πš›πšŽπš’πšπš’πšŽπš, πš’πš—_πš›πšŽπš’πšπš’πšŽπš.

Arguments
πš…π™°πšπšπšŸπšŠπš›
π™»π™Ύπš†πš’πš—πš
πš„π™Ώπš’πš—πš
π™±πšπšŸπšŠπš›
Restrictions
π™»π™Ύπš†β‰€πš„π™Ώ
𝙱β‰₯0
𝙱≀1
Purpose

Enforce the following equivalence, πš…π™°πšβˆˆ[π™»π™Ύπš†,πš„π™Ώ]⇔𝙱.

Example
(3,2,5,1)

The πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•_πš›πšŽπš’πšπš’πšŽπš constraint holds since:

  • Its first argument πš…π™°πš=3 is greater than or equal to its second argument π™»π™Ύπš†=2 and less than or equal to its third argument πš„π™Ώ=5 (i.e.,Β 3∈[2,5]).

  • The corresponding Boolean variable 𝙱 is set to 1 since condition 3∈[2,5] holds.

Typical
πš…π™°πšβ‰ π™»π™Ύπš†
πš…π™°πšβ‰ πš„π™Ώ
π™»π™Ύπš†<πš„π™Ώ
Symmetries
  • An occurrence of a value of πš…π™°πš that belongs to [π™»π™Ύπš†,πš„π™Ώ] (resp. does not belong to [π™»π™Ύπš†,πš„π™Ώ]) can be replaced by any other value in [π™»π™Ύπš†,πš„π™Ώ]) (resp. not in [π™»π™Ύπš†,πš„π™Ώ]).

  • One and the same constant can be added to πš…π™°πš, π™»π™Ύπš† and πš„π™Ώ.

Reformulation

The πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•_πš›πšŽπš’πšπš’πšŽπš constraint can be reformulated in terms of linear constraints. For convenience, we rename πš…π™°πš to x, π™»π™Ύπš† to l, πš„π™Ώ to u, and 𝙱 to y. The constraint is decomposed into the following conjunction of constraints:

xβ‰₯l ⇔y 1 ,x≀u ⇔y 2 ,y 1 ∧y 2 ⇔y .

We show how to encode these constraints with linear inequalities. The first constraint, i.e.,Β xβ‰₯l⇔y 1 is encoded by posting one of the following three constraints:

a) if x Μ²β‰₯l: y 1 =1,b) if x Β―<l: y 1 =0,c) otherwise : xβ‰₯(l-x Μ²)Β·y 1 +x Μ² ∧ x≀(x Β―-l+1)Β·y 1 +l-1.

On the one hand, cases a) and b) correspond to situations where one can fix y 1 , no matter what value will be assigned to x. On the other hand, in case c), y 1 can take both values 0 or 1 depending on the value assigned to x. As shown by FigureΒ 5.154.1, all possible solutions for the pair of variables (x,y 1 ) satisfy the following two linear inequalities xβ‰₯(l-x Μ²)Β·y 1 +x Μ² and x≀(x Β―-l+1)Β·y 1 +l-1. The first inequality discards all points that are above the line that goes through the two extreme solution points (x Μ²,0) and (l,1), while the second one removes all points that are below the line that goes through the two extreme solution points (l-1,0) and (x Β―,1).

Figure 5.154.1. Illustration of the reformulation of the reified constraint xβ‰₯l⇔y 1 with two linear inequalities
ctrs/fig_in_interval_reified_x_geq_l

The second constraint, i.e.,Β x≀u⇔y 2 is encoded by posting one of the following three constraints:

d) if x ¯≀u: y 2 =1,e) if x Μ²>u: y 2 =0,f) otherwise : x≀(u-x Β―)Β·y 2 +x Β― ∧ xβ‰₯(x Μ²-u-1)Β·y 2 +u+1.

On the one hand, cases d) and e) correspond to situations where one can fix y 2 , no matter what value will be assigned to x. On the other hand, in case f), y 2 can take both value 0 or 1 depending on the value assigned to x. As shown by FigureΒ 5.154.2, all possible solutions for the pair of variables (x,y 2 ) satisfy the following two linear inequalities x≀(u-x Β―)Β·y 2 +x Β― and xβ‰₯(x Μ²-u-1)Β·y 2 +u+1. The first inequality discards all points that are above the line that goes through the two extreme solution points (x Β―,0) and (u,1), while the second one removes all points that are below the line that goes through the two extreme solution points (u+1,0) and (x Μ²,1).

Figure 5.154.2. Illustration of the reformulation of the reified constraint x≀u⇔y 2 with two linear inequalities
ctrs/fig_in_interval_reified_x_leq_u

The third constraint, i.e.,Β y 1 ∧y 2 ⇔y is encoded as:

g) yβ‰₯y 1 +y 2 -1,h) y≀y 1 ,i) y≀y 2 .

Case g) handles the implication y 1 ∧y 2 β‡’y, while cases h) and i) take care of the other side yβ‡’y 1 ∧y 2 .

See also

specialisation: πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•.

uses in its reformulation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (bound consistency preserving reformulation).

Keywords

characteristic of a constraint: reified constraint.

constraint arguments: binary constraint.

constraint type: value constraint.

filtering: arc-consistency.