Paper Info
Title
Strong lift-and-project cutting planes for the stable set problem.
Abstract
A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of two extreme situations: either provide weak bounds at low computational cost or give good bounds (sometimes excellent) but too demanding to compute. In this paper we present a method to bridge such a gap. In particular, a new lift-and-project relaxation is obtained by a problem-specific variant of the lifting operator M(K, K) by Lovász and Schrijver, combined with Benders decomposition. This yields strong cutting planes, generated by solving a cut generating linear program. An extensive computational experience shows that embedding these cuts in a branch-and-cut framework significantly reduces the size of the enumeration trees as well as the CPU times with respect to state-of-the-art IP algorithms.
Year
DOI
Venue
2013
10.1007/s10107-012-0513-3
Math. Program.
Keywords
Field
DocType
Stable set problem, Cutting planes, Lovász and Schrijver lift-and-project operators, Benders decomposition, 90C10 (integer programming), 90C57 (polyhedral combinatorics, branch-and-bound, branch-and-cut)
Lift (force),Discrete mathematics,Combinatorics,Mathematical optimization,Central processing unit,Embedding,Integer programming,Operator (computer programming),Linear programming,Polyhedral combinatorics,Semidefinite programming,Mathematics
Journal
Volume
Issue
ISSN
141
1-2
1436-4646
Citations 
PageRank 
References 
7
0.48
26
Authors
3
Name
Order
Citations
PageRank
Monia Giandomenico1303.74
Fabrizio Rossi214016.33
Stefano Smriglio315314.81