Photo from wikipedia
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… Click to show full 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.
Keywords:
wheel inequalities;
inequalities stable;
formulation;
wheel;
set polytope;
stable set
Journal Title: Networks
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Networks
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!