Standard
Strengthening Chvátal-Gomory cuts for the stable set problem. /
Letchford, Adam Nicholas; Marzi, Francesca; Rossi, Fabrizio et al.
Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers. ed. / Raffele Cerulli; Satoru Fujishige; A.Ridha Mahjoub. Berlin: Springer, 2016. p. 201-212 (Lecture Notes in Computer Science; Vol. 9849).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review
Harvard
Letchford, AN, Marzi, F, Rossi, F & Smriglio, S 2016,
Strengthening Chvátal-Gomory cuts for the stable set problem. in R Cerulli, S Fujishige & AR Mahjoub (eds),
Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9849, Springer, Berlin, pp. 201-212.
https://doi.org/10.1007/978-3-319-45587-7_18
APA
Letchford, A. N., Marzi, F., Rossi, F., & Smriglio, S. (2016).
Strengthening Chvátal-Gomory cuts for the stable set problem. In R. Cerulli, S. Fujishige, & A. R. Mahjoub (Eds.),
Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers (pp. 201-212). (Lecture Notes in Computer Science; Vol. 9849). Springer.
https://doi.org/10.1007/978-3-319-45587-7_18
Vancouver
Letchford AN, Marzi F, Rossi F, Smriglio S.
Strengthening Chvátal-Gomory cuts for the stable set problem. In Cerulli R, Fujishige S, Mahjoub AR, editors, Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers. Berlin: Springer. 2016. p. 201-212. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-45587-7_18
Author
Letchford, Adam Nicholas ; Marzi, Francesca ; Rossi, Fabrizio et al. /
Strengthening Chvátal-Gomory cuts for the stable set problem. Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers. editor / Raffele Cerulli ; Satoru Fujishige ; A.Ridha Mahjoub. Berlin : Springer, 2016. pp. 201-212 (Lecture Notes in Computer Science).
Bibtex
@inbook{938c11ce1cff40a9af9cdd1b946164c7,
title = "Strengthening Chv{\'a}tal-Gomory cuts for the stable set problem",
abstract = "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{\'a}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.",
keywords = "combinatorial optimisation, stable set problem, cutting planes",
author = "Letchford, {Adam Nicholas} and Francesca Marzi and Fabrizio Rossi and Stefano Smriglio",
year = "2016",
month = sep,
day = "10",
doi = "10.1007/978-3-319-45587-7_18",
language = "English",
isbn = "9783319455860",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "201--212",
editor = "Raffele Cerulli and Satoru Fujishige and A.Ridha Mahjoub",
booktitle = "Combinatorial Optimization",
}
RIS
TY - CHAP
T1 - Strengthening Chvátal-Gomory cuts for the stable set problem
AU - Letchford, Adam Nicholas
AU - Marzi, Francesca
AU - Rossi, Fabrizio
AU - Smriglio, Stefano
PY - 2016/9/10
Y1 - 2016/9/10
N2 - 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.
AB - 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.
KW - combinatorial optimisation
KW - stable set problem
KW - cutting planes
U2 - 10.1007/978-3-319-45587-7_18
DO - 10.1007/978-3-319-45587-7_18
M3 - Chapter (peer-reviewed)
SN - 9783319455860
T3 - Lecture Notes in Computer Science
SP - 201
EP - 212
BT - Combinatorial Optimization
A2 - Cerulli, Raffele
A2 - Fujishige, Satoru
A2 - Mahjoub, A.Ridha
PB - Springer
CY - Berlin
ER -
