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.
https://hal.inria.fr/inria-00070518
Contributeur : Jérôme Malick
<>
Soumis le : lundi 25 mars 2013 - 14:27:01
Dernière modification le : mercredi 11 avril 2018 - 01:58:33
Document(s) archivé(s) le : mercredi 26 juin 2013 - 04:01:26
