Another Absolute Value Question

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

The following two tabs change content below.
I'm an apostate mathematician, retired from a business school after 33 years of teaching mostly (but not exclusively) quantitative methods courses. My academic interests lie in operations research. I also study Tae Kwon Do a bit on the side.

Latest posts by Paul Rubin (see all)