2
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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<j} 2q_{ij}z_{ij} $$

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – KGM
    Mar 7 at 10:33
  • $\begingroup$ I have detailed the values of $Q$ in the 2-dimensional case. $\endgroup$
    – Kuifje
    Mar 7 at 11:12
  • $\begingroup$ 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. $\endgroup$
    – KGM
    Mar 7 at 11:44
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Mar 7 at 12:41
  • $\begingroup$ 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. $\endgroup$
    – KGM
    Mar 7 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.