Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem

Alexander Engau, Miguel F. Anjos, Immanuel Bomze

Résultat de recherche: Articleexamen par les pairs

4 Citations (Scopus)

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'origineEnglish
Pages (de-à)35-59
Nombre de pages25
JournalMathematical Methods of Operations Research
Volume78
Numéro de publication1
DOI
Statut de publicationPublished - août 2013
Publié à l'externeOui

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

Empreinte numérique

Plonger dans les sujets de recherche 'Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem'. Ensemble, ils forment une empreinte numérique unique.

Citer

Engau, A., Anjos, M. F., & Bomze, I. (2013). Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem. Mathematical Methods of Operations Research, 78(1), 35-59. https://doi.org/10.1007/s00186-013-0431-z