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

https://hal.inria.fr/inria-00070518
Contributor : Jérôme Malick <>
Submitted on : Monday, March 25, 2013 - 2:27:01 PM
Last modification on : Tuesday, February 9, 2021 - 3:20:06 PM
Long-term archiving on: : Wednesday, June 26, 2013 - 4:01:26 AM

File

07-malick.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

563

Files downloads

1532