Résumé
The stable-set problem is an NP-hard problem that arises in numerous areas such as social networking, electrical engineering, environmental forest planning, bioinformatics clustering and prediction, and computational chemistry. While some relaxations provide high-quality bounds, they result in very large and expensive conic optimization problems. We describe and test an integrated interior-point cutting-plane method that efficiently handles the large number of nonnegativity constraints in the popular doubly-nonnegative relaxation. This algorithm identifies relevant inequalities dynamically and selectively adds new constraints in a build-up fashion. We present computational results showing the significant benefits of this approach in comparison to a standard interior-point cutting-plane method.
Langue d'origine | English |
---|---|
Pages (de-à) | 35-59 |
Nombre de pages | 25 |
Journal | Mathematical Methods of Operations Research |
Volume | 78 |
Numéro de publication | 1 |
DOI | |
Statut de publication | Published - août 2013 |
Publié à l'externe | Oui |
Note bibliographique
Funding Information:Miguel F. Anjos: Research partially supported by the Natural Sciences and Engineering Research Council of Canada, and by a Humboldt Research Fellowship.
Funding Information:
Alexander Engau: Research partially supported by the DFG Emmy Noether project “Combinatorial Optimization in Physics (COPhy)” at the University of Cologne, Germany and by MITACS, a Network of Centres of Excellence for the Mathematical Sciences in Canada.
ASJC Scopus Subject Areas
- Software
- General Mathematics
- Management Science and Operations Research