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 !


Non-convex quadratic programming problems with bounds constraints are in general NP-Hard. Thus you shouldn't expect to find a polynomial time algorithm for this problem.

These problems can be addressed by various heuristic approaches or by branch and bound methods (although this requires considerable computational effort.)

How large are the instances that you're interested in?

  • $\begingroup$ Thanks. Since the LP relaxed problem (by defining $y_{ij}=x_ix_j$ for example) can be efficiently solved (optimal solution are half-integral), I was expecting the same thing without using $y_{ij}$. The order of $i$ is of hundreds. $\endgroup$
    – Khue
    Oct 5 '15 at 16:02
  • $\begingroup$ You can certainly relax with $y_{ij}=x_{i}x_{j}$ to get an LP relaxation, but that relaxation provides only a lower bound on the optimal value. The issue is that the $y_{ij}$ values that are optimal might not have a corresponding $x$ vector such that $y_{ij}=x_{i}x_{j}$ for all $i$ and $j$. e.g. you could have $y_{12}=1$ and $y_{13}=0$ and $y_{23}=1$ in the optimal solution to the LP relaxation. $\endgroup$ Oct 5 '15 at 16:17
  • $\begingroup$ Definitely agree with this analysis. If the $a_{ij}$ form a positive semidefinite matrix, then Problem 2 could be solved to global optimality in polynomial time. For sufficiently small and/or structured instances, it might be possible to solve the MIQP in Problem 1 in a reasonable amount of time (e.g., using Gurobi or CPLEX, with branch-and-bound methods), but not in the classical sense of "efficient", because the problem is NP-hard. $\endgroup$ Oct 5 '15 at 21:57
  • $\begingroup$ As I've answered on math.stackexchange.com/questions/1465675/…, the answer is practically yes, as you always can reformulate the binary QP, with very little computational effort, to ensure that the convex relaxation is convex, and thus efficiently solvable. $\endgroup$ Oct 6 '15 at 6:20
  • $\begingroup$ Johan is write that you can produce a convex QP relaxation easily. However, problem 2 in the question above convex- you have to alter the coefficients to get a convex relaxation. $\endgroup$ Oct 6 '15 at 14:15

The problem turns into an instance of Supermodular minimization if the constants $a_i$ and $a_{ij}$ are positive. It still remains NP-hard but there are guarantees for the greedy approach based solution.


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.