Quadratic Pseudo-Boolean Optimization (QPBO) problem:

Problem 1. Minimize $\sum_i a_ix_i + \sum_{i<j} a_{ij}x_i x_j$ subject to $x_i\in\{0,1\}\forall i$.

Consider the following problem, where the integral constraints are relaxed:

Problem 2. Minimize $\sum_i a_ix_i + \sum_{i<j} a_{ij}x_i x_j$ subject to $0\le x_i\le 1\forall i$.

My question is whether there exists an efficient method that can solve Problem 2 exactly (i.e. output an optimal solution)?

Thank you in advance for any suggestions !


No, Problem 2 is a nonconvex quadratic program (bilinear to be specific) which is known to be hard.

However, you can always start by preprocessing Problem 1 to ensure that the continuous relaxation is convex. You can do this by adding terms $\lambda_i x_i^2 - \lambda_i x_i$ to the objective. This term is zero on the binary lattice and thus leaves the original problem unchanged, but with sufficiently large $\lambda_i$, the continuous relaxation is a convex quadratic program, and thus easy to solve.

  • $\begingroup$ Thanks, Johan. The above relaxation is a pretty nice idea. $\endgroup$ – Khue Oct 6 '15 at 16:26
  • $\begingroup$ Hi Johan. I have encountered a problem and remembered your answer because it's related. Could you please provide me with references on the above continuous relaxation? I think (but might be wrong) it's not a very good relaxation since it favors fractional solutions (if $\lambda_i$ is large enough then $x_i$ cannot be $0$ or $1$, it's preferably 0.5 actually, which is not good). Thanks. $\endgroup$ – Khue Feb 8 '16 at 21:58
  • $\begingroup$ It is so basic that I cannot think of any direct reference. It is essentially part of the "without loss of generality" part of papers. Just googling and taking the first paper leads to A Recipe for Semidefinite Relaxation for (0,1)-Quadratic Programming by Poljak,Rendl and Wolkowicz, introduced without any direct reference $\endgroup$ – Johan Löfberg Feb 9 '16 at 10:04
  • $\begingroup$ Thanks again. (Some more characters...) $\endgroup$ – Khue Feb 16 '16 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.