5.154. in_interval_reified

 DESCRIPTION LINKS
Origin
Constraint

$\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi },\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ},\mathrm{\pi ±}\right)$

Synonyms

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$.

Arguments
 $\mathrm{\pi  \pi °\pi }$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi »\pi Ύ\pi }$ $\mathrm{\pi \pi \pi }$ $\mathrm{\pi \pi Ώ}$ $\mathrm{\pi \pi \pi }$ $\mathrm{\pi ±}$ $\mathrm{\pi \pi \pi \pi }$
Restrictions
 $\mathrm{\pi »\pi Ύ\pi }\beta €\mathrm{\pi \pi Ώ}$ $\mathrm{\pi ±}\beta ₯0$ $\mathrm{\pi ±}\beta €1$
Purpose

Enforce the following equivalence, $\mathrm{\pi  \pi °\pi }\beta \left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]\beta \mathrm{\pi ±}$.

Example
$\left(3,2,5,1\right)$

The $\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint holds since:

• Its first argument $\mathrm{\pi  \pi °\pi }=3$ is greater than or equal to its second argument $\mathrm{\pi »\pi Ύ\pi }=2$ and less than or equal to its third argument $\mathrm{\pi \pi Ώ}=5$ (i.e.,Β $3\beta \left[2,5\right]$).

• The corresponding Boolean variable $\mathrm{\pi ±}$ is set to 1 since condition $3\beta \left[2,5\right]$ holds.

Typical
 $\mathrm{\pi »\pi Ύ\pi }<\mathrm{\pi \pi Ώ}$
Symmetries
• An occurrence of a value of $\mathrm{\pi  \pi °\pi }$ that belongs to $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$ (resp. does not belong to $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$) can be replaced by any other value in $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$) (resp. not in $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$).

• One and the same constant can be added to $\mathrm{\pi  \pi °\pi }$, $\mathrm{\pi »\pi Ύ\pi }$ and $\mathrm{\pi \pi Ώ}$.

Reformulation

The $\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint can be reformulated in terms of linear constraints. For convenience, we rename $\mathrm{\pi  \pi °\pi }$ to $x$, $\mathrm{\pi »\pi Ύ\pi }$ to $l$, $\mathrm{\pi \pi Ώ}$ to $u$, and $\mathrm{\pi ±}$ to $y$. The constraint is decomposed into the following conjunction of constraints:

$\begin{array}{cc}& x\beta ₯l\beta {y}_{1},\hfill \\ & x\beta €u\beta {y}_{2},\hfill \\ & {y}_{1}\beta §{y}_{2}\beta y.\hfill \end{array}$

We show how to encode these constraints with linear inequalities. The first constraint, i.e.,Β $x\beta ₯l\beta {y}_{1}$ is encoded by posting one of the following three constraints:

$\left\{\begin{array}{ccc}\mathrm{a}\right)\hfill & \hfill \mathrm{if}\underset{Μ²}{x}\beta ₯l:& {y}_{1}=1,\hfill \\ \mathrm{b}\right)\hfill & \hfill \mathrm{if}\stackrel{Β―}{x}

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 $\left(x,{y}_{1}\right)$ satisfy the following two linear inequalities $x\beta ₯\left(l-\underset{Μ²}{x}\right)Β·{y}_{1}+\underset{Μ²}{x}$ and $x\beta €\left(\stackrel{Β―}{x}-l+1\right)Β·{y}_{1}+l-1$. The first inequality discards all points that are above the line that goes through the two extreme solution points $\left(\underset{Μ²}{x},0\right)$ and $\left(l,1\right)$, while the second one removes all points that are below the line that goes through the two extreme solution points $\left(l-1,0\right)$ and $\left(\stackrel{Β―}{x},1\right)$.

The second constraint, i.e.,Β $x\beta €u\beta {y}_{2}$ is encoded by posting one of the following three constraints:

$\left\{\begin{array}{ccc}\mathrm{d}\right)\hfill & \hfill \mathrm{if}\stackrel{Β―}{x}\beta €u:& {y}_{2}=1,\hfill \\ \mathrm{e}\right)\hfill & \hfill \mathrm{if}\underset{Μ²}{x}>u:& {y}_{2}=0,\hfill \\ \mathrm{f}\right)\hfill & \hfill \mathrm{otherwise}:& x\beta €\left(u-\stackrel{Β―}{x}\right)Β·{y}_{2}+\stackrel{Β―}{x}\beta §x\beta ₯\left(\underset{Μ²}{x}-u-1\right)Β·{y}_{2}+u+1.\hfill \end{array}\right\$

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 $\left(x,{y}_{2}\right)$ satisfy the following two linear inequalities $x\beta €\left(u-\stackrel{Β―}{x}\right)Β·{y}_{2}+\stackrel{Β―}{x}$ and $x\beta ₯\left(\underset{Μ²}{x}-u-1\right)Β·{y}_{2}+u+1$. The first inequality discards all points that are above the line that goes through the two extreme solution points $\left(\stackrel{Β―}{x},0\right)$ and $\left(u,1\right)$, while the second one removes all points that are below the line that goes through the two extreme solution points $\left(u+1,0\right)$ and $\left(\underset{Μ²}{x},1\right)$.

The third constraint, i.e.,Β ${y}_{1}\beta §{y}_{2}\beta y$ is encoded as:

$\left\{\begin{array}{cc}\mathrm{g}\right)\hfill & y\beta ₯{y}_{1}+{y}_{2}-1,\hfill \\ \mathrm{h}\right)\hfill & y\beta €{y}_{1},\hfill \\ \mathrm{i}\right)\hfill & y\beta €{y}_{2}.\hfill \end{array}\right\$

Case g) handles the implication ${y}_{1}\beta §{y}_{2}\beta y$, while cases h) and i) take care of the other side $y\beta {y}_{1}\beta §{y}_{2}$.

See also

uses in its reformulation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β (bound consistency preserving reformulation).

Keywords