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)\)
\(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\).