# Solving a quadratic pseudo-boolean optimization problem where the integral constraints are relaxed

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?

• 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.
– f10w
Oct 5, 2015 at 16:02
• 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. Oct 5, 2015 at 16:17
• 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. Oct 5, 2015 at 21:57
• 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. Oct 6, 2015 at 6:20
• 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. Oct 6, 2015 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.