0

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 !

f10w
  • 4,509
  • 15
  • 22

1 Answers1

3

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.

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
  • Thanks, Johan. The above relaxation is a pretty nice idea. – f10w Oct 06 '15 at 16:26
  • 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. – f10w Feb 08 '16 at 21:58
  • 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 – Johan Löfberg Feb 09 '16 at 10:04
  • Thanks again. (Some more characters...) – f10w Feb 16 '16 at 09:25