Saturday, October 9, 2010

Binary Variables and Quadratic Terms

Generally speaking, if $x$ and $y$ are variables in a mathematical program, and you want to deal with their product $z=x y$, you will end up having a quadratic problem (which may create problems with convexity if the quadratic terms appear in constraints). There is a special case, though, when at least one of $x$ and $y$ is binary, and when the other variable is bounded. Under those assumptions, the product can be linearized.

Let $x$ be binary and let $L\le y \le U$ where $L$ and $U$ are bounds known in advance. Introduce a new variable $z$. (Programming note: Regardless of whether $y$ is real-valued, integer-valued or binary, $z$ can be treated as real-valued.) Add the following four constraints: \begin{eqnarray*} z & \le & Ux \\ z & \ge & Lx \\ z & \le & y - L(1-x) \\ z & \ge & y - U(1-x). \end{eqnarray*}
Consider first the case $x=0$, which means the product $z = x y$ should be $0$. The first pair of inequalities says $0 \le z \le 0$, forcing $z=0$. The second pair of inequalities says $y-U \le z \le y - L$, and $z=0$ satisfies those inequalities.

Now consider the case $x=1$, so that the product should be $z = y$. The first pair of inequalities becomes $L \le z \le U$, which is satisfied by $z = y$. The second pair says $y \le z \le y$, forcing $z= y$ as desired.