Thursday, May 15, 2008

Multiplication of a continuous and a binary variable

The expression \(z = x \cdot \delta \) where \(x\) is a continuous variable and \(\delta\) is a binary variable can also be linearized fairly easily. The exact form depends on the bounds of \(x\). Assume \(x\) has lower bound \(x^{lo}\) and upper bound \(x^{up}\), then we can form the inequalities:
\[\boxed{\begin{split}\min\{0,x^{lo}\} &\le z \le \max\{0,x^{up}\} \\
x^{lo} \cdot \delta &\le z \le x^{up} \cdot \delta \\
x − x^{up} \cdot (1 − \delta) &\le z \le x − x^{lo} \cdot (1 − \delta)\end{split}}\]
The last restriction is essentially a big-M constraint:
\[\boxed{x − M_1 \cdot (1 − \delta) \le z \le x + M_2 \cdot (1 − \delta)}\]
where \(M_1\), \(M_2\) are chosen as tightly as possible while not excluding \(z=0\) when \(\delta=0\).

For the special case \(x^{lo}=0\) this reduces to:
\[\boxed{\begin{split}& z \in [0,x^{up}]\\ & z ≤ x^{up} · \delta\\ & z ≤ x\\ & z ≥ x − x^{up} · (1 − \delta)\end{split}}\]
The construct \(z=x· \delta\) can be used to model an OR condition: "\(z = 0\) OR \(z = x\)".