**binary variables**is as follows:

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.

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

Another weaker formulation that is sometimes used is:

This formulation has fewer equations but has two major disadvantages:

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

- \(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:

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

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

See http://www.lib.ncsu.edu/theses/available/etd-11042008-151506/unrestricted/etd.pdf for some computational experiments with this formulation.

ReplyDelete