An extended formulation for the 1‐wheel inequalities of the stable set polytope. Issue 1 (17th October 2019)

• Record Type: Journal Article
• Authors: de Vries, Sven; Friedrich, Ulf; Perscheid, Bernd
• Is Part Of: Networks. Volume 75:Issue 1(2020)
• Page Start: 86
• Page End: 94
• Publication Date: 2019-10-17
• Subjects: extended formulation -- graph product -- polyhedral combinatorics -- separation problem -- stable set problem -- wheel inequalities; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21906
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: The 1‐wheel inequalities for the stable set polytope were introduced by Cheng and Cunningham. In general, there is an exponential number of these inequalities. We present a new polynomial size extended formulation of the stable set relaxation that includes the odd cycle and 1‐wheel inequalities. This compact formulation allows one to polynomially optimize over a polyhedron instead of handling the separation problem for 1‐wheel inequalities by solving many shortest walk problems and relying on the ellipsoid method.