Home > Research > Publications & Outputs > Strengthening Chvátal-Gomory cuts for the stabl...

Electronic data


Text available via DOI:

View graph of relations

Strengthening Chvátal-Gomory cuts for the stable set problem

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)peer-review

Publication date10/09/2016
Host publicationCombinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers
EditorsRaffele Cerulli, Satoru Fujishige, A.Ridha Mahjoub
Place of PublicationBerlin
Number of pages12
ISBN (electronic)9783319455877
ISBN (print)9783319455860
<mark>Original language</mark>English

Publication series

NameLecture Notes in Computer Science


The stable set problem is a well-known NP-hard combinatorial optimization problem. As well as being hard to solve (or even approximate) in theory, it is often hard to solve in practice. The main difficulty is that upper bounds based on linear programming (LP) tend to be weak, whereas upper bounds based on semidefinite programming (SDP) take a long time to compute. We propose a new method to strengthen the LP-based upper bounds. The key idea is to take violated Chvátal-Gomory cuts and then strengthen their right-hand sides. Although the strengthening problem is itself NP-hard, it can be solved reasonably quickly in practice. As a result, the overall procedure proves to be capable of yielding competitive upper bounds in reasonable computing times.