Skip to Main content Skip to Navigation
Journal articles

The Spherical Constraint in Boolean Quadratic Programs

Jérôme Malick 1 
1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Jérôme Malick Connect in order to contact the contributor
Submitted on : Monday, March 25, 2013 - 2:27:01 PM
Last modification on : Thursday, January 20, 2022 - 5:28:36 PM
Long-term archiving on: : Wednesday, June 26, 2013 - 4:01:26 AM


Files produced by the author(s)




Jérôme Malick. The Spherical Constraint in Boolean Quadratic Programs. Journal of Global Optimization, Springer Verlag, 2007, 39 (4), pp.609-622. ⟨10.1007/s10898-007-9161-1⟩. ⟨inria-00070518v2⟩



Record views


Files downloads