Multiplication of binary variables

I see often MINLP models where the only nonlinear expression is the multiplication of two binary variables. Such models can be linearized quite easily and are in most cases better solved as a linear MIP model. A good formulation for \(z=x_1 \cdot x_2\) where \(x_1\), \(x_2\) are binary variables is as follows:

\[\boxed{\begin{split}0 &≤ z ≤ 1\\ z &≤ x_1\\ z &≤ x_2\\ z &≥ x_1 + x_2 − 1\end{split}}\]

Notice that we relaxed \(z\) to be continuous between 0 and 1: \(z\) is automatically integer; a property we can use to reduce the number of discrete variable. Note that modern high performance solvers may reintroduce these variables as binary as they can exploit this in their algorithms.

Another weaker formulation that is sometimes used is:

\[\boxed{\begin{split}z &\in \{0,1\}\\ z & ≤ \frac{x_1+x_2}{2}\\z &≥ x_1 + x_2 − 1\end{split}}\]

This formulation has fewer equations but has two major disadvantages:

• \(z\) needs to be integer
• it is not as tight as the first formulation. E.g. \((x_1,x_2,z)=(0,1,\frac{1}{2})\) is infeasible in the first formulation, while it is allowed in relaxations of the second formulation.

An application of this reformulation is a QP (Quadratic Program) with binary variables:

\[\boxed{\begin{split} \min\> & x'Qx\\ & Ax=b\\ & x \in \{0,1\} \end{split}}\]

This can be modeled as:

variable y(i,j);
 
set ij(i,j);
ij(i,j)$( ord(i)<ord(j) ) = yes;
 
y.lo(ij)=0;
y.up(ij)=1;
 
obj..   z =e= sum(i, q(i,i)*x(i)) + sum(ij(i,j), (q(i,j)+q(j,i))*y(i,j) );
ymul1(ij(i,j)).. y(i,j) =L= x(i);
ymul2(ij(i,j)).. y(i,j) =L= x(j);
ymul3(ij(i,j)).. y(i,j) =G= x(i)+x(j)-1;

The more general product \(z = \prod_i x_i\) with \(x_i\in \{0,1\}\) can be linearized in the same way:

\[\boxed{\begin{split} &z ≤ x_i\\ & z ≥ \sum_i x_i – (n-1)\\& z \in \{0,1\}\end{split}}\]

where \(n\) is the cardinality of the set \(I\). Again if we want we can relax \(z\) to \(z \in [0,1]\).