# Relaxed quadratic pseudo-boolean optimization

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 !

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.
• 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. – Khue Feb 8 '16 at 21:58