Written by: Paul Rubin

Primary Source: OR in an OB World

Someone asked whether it is possible to eliminate the absolute value from the constraint

\(Lx\le |y| \le Ux\)

(where \(L\ge 0\) and \(U>0\) are constants, \(x\) is a binary variable, and \(y\) is a continuous variable). The answer is yes, but what it takes depends on whether \(L=0\) or \(L>0\).

The easy case is when \(L=0\). There are two possibilities for the domain of \(y\): either \(y\in [0,0]\) (if \(x=0\)) or \(y\in [-U,U]\) (if \(x=1\)). One binary variable is enough to capture two choices, so we don’t need any new variables. We just need to rewrite the constraint as

\(-Ux\le y \le Ux.\)

If \(L>0\), then there are *three* possibilities for the domain of \(y\): \([-U, -L] \cup [0,0] \cup [L, U]\). That means we’ll need at least two binary variables to cover all choices. Rather than change the interpretation of \(x\) (which may be used elsewhere in the questioner’s model), I’ll introduce two new binary variables (\(z_1\) for the left interval and \(z_2\) for the right interval) and link them to \(x\) via \(x=z_1+z_2\). That leads to the following constraints:

\(-Uz_1 \le y \le -Lz_1 + U(1-z_1)\)

and

\(Lz_2 – U(1-z_2) \le y \le Uz_2.\)

If \(x=0\), both \(z_1\) and \(z_2\) must be 0, and the new constraints force \(y=0\). If \(x=1\), then either \(z_1=1\) or \(z_2=1\) (but not both). Left to the reader as an exercise: verify that \(z_1=1\Longrightarrow -U\le y \le -L\) while \(z_2=1 \Longrightarrow L\le y\le U\).

#### Paul Rubin

#### Latest posts by Paul Rubin (see all)

- Threads and Memory - January 28, 2019
- Of Typewriters and Permutations (V) - December 17, 2018
- Of Typewriters and Permutations (IV) - December 17, 2018