How to convert the following Quadratic optimization problem to a linear one?

Question

I have an optimization problem

$$Min : \ 3x_{11} + 5x_{12} + 4x_{21} + 3 x_{22} - (10x_{11}x_{22} + 2x_{12}x_{21})$$ subject to the following constraints :

$$ x_{11} + x_{12} = 1$$ $$ x_{21} + x_{22} = 1$$

where $x_{11}. x_{12}, x_{21}, x_{22}$ are Integer Variables taking values either $0$ or $1$.

How do I convert the objective function to a linear one?

Answer 1

Observe that $x_{11}x_{22}= 1$ if and only if $x_{11}=x_{22}=1$. Define new binary variables $z_1$, $z_2$, replace $x_{11}x_{22}$ with $z_1$, replace $x_{12}x_{21}$ with $z_2$, and add the following constraints:

\begin{align} z_1 &\leqslant x_{11}\tag1\\ z_1 &\leqslant x_{22}\tag2\\ z_1 &\geqslant x_{11}+x_{22}-1\tag3\\ z_2 &\leqslant x_{12}\tag4\\ z_2 &\leqslant x_{21}\tag5\\ z_2 &\geqslant x_{12}+x_{21}-1\tag6. \end{align} Constraints $(1)$ and $(2)$ ensures that $z_1$ can only take value $1$ when $x_{11}=x_{22}=1$. Constraint $(3)$ ensures that $z_1$ actually does take values $1$ when $x_{11}=x_{22}=1$. Constraints $(4)$, $(5)$, and $(6)$ play a similar role for $z_2$. Our resulting binary integer program is \begin{align} \min&\quad 3x_{11}+5x_{12} + 4x_{21} + 3x_{22} -10z_1 -2z_2\\ \mathrm{s.t.}&\quad x_{11}+x_{12} = 1\\ &\quad x_{21} + x_{22} =1\\ &\quad z_1 \leqslant x_{11}\\ &\quad z_1 \leqslant x_{22}\\ &\quad z_1 \geqslant x_{11}+x_{22}-1\\ &\quad z_2 \leqslant x_{12}\\ &\quad z_2 \leqslant x_{21}\\ &\quad z_2 \geqslant x_{12}+x_{21}-1\\ &\quad x_{11},x_{12},x_{21},x_{22},z_1,z_2\in\{0,1\}. \end{align} Adding slack variables to convert this into the standard form $\{\min c^Tx : Ax=b, x\geqslant 0\}$, we have \begin{align} \min&\quad 3x_{11}+5x_{12} + 4x_{21} + 3x_{22} -10z_1 -2z_2\\ \mathrm{s.t.}&\quad x_{11}+x_{12} = 1\\ &\quad x_{21} + x_{22} =1\\ &\quad -x_{11}+z_1 + s_1 = 0\\ &\quad - x_{22} +z_1 + s_2 =0\\ &\quad x_{11}+x_{22}-z_1 + s_3 = 1\\ &\quad - x_{12} +z_2 + s_4 = 0\\ &\quad - x_{21}+z_2 + s_5 = 0\\ &\quad x_{12}+x_{21} - z_2 + s_6 = 1\\ &\quad x_{11},x_{12},x_{21},x_{22},z_1,z_2\in\{0,1\}. \end{align} We have $$ c = \begin{pmatrix}3&5&4&3&-10&-2&0&0&0&0&0&0\end{pmatrix}^T, $$ $$ b = \begin{pmatrix}1&1&0&0&1&0&0&1 \end{pmatrix}^T, $$ and $$ A = \left( \begin{array}{cccccccccccc} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right). $$ It turns out that $A$ is totally unimodular (as verified by the $\texttt{is_totally_unimodular}$ function in the $\texttt{lintools}$ package of $\texttt R$. Since $b$ is integral, every vertex of the polytope $\{Ax=b,x\geqslant 0\}$ is integral, so we may solve this integer program by general linear programming methods. Indeed an optimal basis is $(x_{11},1_{22},z_1,s_6) = (1,1,1,1)$ with objective value $-4$.

Answer 2

The general linearization of a product of binary variables is overkill here. Instead, first substitute $x_{12} = 1 - x_{11}$ and $x_{22} = 1 - x_{21}$ to obtain objective function \begin{align} &3x_{11} + 5x_{12} + 4x_{21} + 3 x_{22} - 10x_{11}x_{22} - 2x_{12}x_{21}\\ &=3x_{11} + 5(1 - x_{11}) + 4x_{21} + 3 (1 - x_{21}) - 10x_{11}(1 - x_{21}) - 2(1 - x_{11})x_{21}\\ &=3x_{11} + 5 - 5 x_{11} + 4x_{21} + 3 - 3 x_{21} - 10x_{11} +10x_{11} x_{21} - 2x_{21} +2 x_{11} x_{21}\\ &=8 - 12x_{11} - x_{21} +12x_{11} x_{21}. \end{align} Now introduce $y \ge 0$ to represent $x_{11} x_{21}$. Because we are minimizing, and the objective coefficient is $12>0$, we need only enforce $y\ge x_{11} x_{21}$, which we can do with a single linear constraint $y\ge x_{11} + x_{21} - 1$. In summary, the problem is to minimize $$8 - 12x_{11} - x_{21} +12y$$ subject to: \begin{align} y&\ge x_{11} + x_{21} - 1\\ x_{11} &\in \{0,1\}\\ x_{12} &\in \{0,1\}\\ y &\ge 0 \end{align} The optimal solution is $(x_{11},x_{21},y)=(1,0,0)$, which yields objective value $-4$ and corresponds to $(x_{11},x_{12},x_{21},x_{22})=(1,0,0,1)$ in the original space.