Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 35-59 |
| Number of pages | 25 |
| Journal | Mathematical Methods of Operations Research |
| Volume | 78 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Aug 2013 |
| Externally published | Yes |
Bibliographical note
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