The Spherical Constraint in Boolean Quadratic Programs

Abstract : We propose a new approach to bound Boolean quadratic optimization problems. The idea is to re-express Boolean constraints as one ''spherical'' constraint. Dualizing this constraint then amounts to a semidefinite least-squares problem which can be efficiently solved. Studying this dualization also provides an alternative interpretation of the relaxation and reveals a new class of non-convex problems with no duality gap.