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 !
Solving a quadratic pseudo-boolean optimization problem where the integral constraints are relaxed
optimization
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? 