# How to transform a binary QP into an MILP?

I have a binary quadratic problem with objective $${\bf{x}}^T{\bf{Qx}}+{\bf{c}}^T{\bf{x}}$$

subject to

$${\bf{A}}{\bf{x}}\le{\bf{b}}$$

$${\bf{A}}_{eq}{\bf{x}}={\bf{b}}_{eq}$$.

here $${\bf{x}}$$ is binary.

From https://support.gurobi.com/hc/en-us/community/posts/7015136566801-Binary-Quadratic-Programming, we know that we can transform this binary QP into a binary linear problem.

For my QP problem, then what will be objective function for the binary linear problem?

is it

$$\sum{\bf{Qy}}+{\bf{c}}^T{\bf{y}}$$?

where $${\bf{y}}$$ is new variable for linearizing the multiplication of binary variables.

For simplicity, lets assume $$Q$$ is a $$2$$ dimensional matrix: $$x^TQx = \begin{pmatrix} x_1 & x_2 \\ \end{pmatrix} \begin{pmatrix} q_{11} & q_{12} \\ q_{12} & q_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} =q_{11}x_1^2+q_{22}x_2^2+2q_{12}x_1x_2$$

So your objective function looks like: $$q_{11}x_1^2+q_{22}x_2^2+2q_{12}x_1x_2 +c_1x_1 +c_2x_2$$

Since $$x_i$$ are binaries, you can simplify to: $$q_{11}x_1+q_{22}x_2+2q_{12}x_1x_2 +c_1x_1 +c_2x_2 = (q_{11}+c_1)x_1 + (q_{22}+c_2)x_2 + 2q_{12}x_1x_2$$

The last step is to use the linearization trick described in the link your provided for $$x_1x_2$$:

$$(q_{11}+c_1)x_1 + (q_{22}+c_2)x_2 + 2q_{12}z_{12}$$

with \begin{align} z_{12} &\le x_1 \\ z_{12} &\le x_2 \\ z_{12} &\ge x_1 +x_2-1 \end{align}

More generally, the objective function can be written as follows: $$\sum_i(q_{ii}+c_i)x_i + \sum_{i,j|i

• would you please explain. Where does $Q$ go? What is $c_{i,j}$ as we have only $c_i$? What are $a_i$, $b_i$ here?
– KGM
Commented Mar 7 at 10:33
• I have detailed the values of $Q$ in the 2-dimensional case. Commented Mar 7 at 11:12
• Really nice! Please not that we may not have $q_{1,2}=q_{2,1}$. Would you please provide a more generalized and compact form for the objective function.
– KGM
Commented Mar 7 at 11:44
• it would be surprising that matrix is not symmetric ($q_{12} \neq q_{21}$). en.wikipedia.org/wiki/Quadratic_programming. I have added the generalized form for the objective function. Commented Mar 7 at 12:41
• thanks a lot. For the second term in the objective, both I and j range from 1 to 2 (according to this example)? Or its I ranges from 1 to 2, and j>i.
– KGM
Commented Mar 7 at 22:35