Inhaltszusammenfassung

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 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.» weiterlesen» einklappen

Autoren

Klassifikation

DFG Fachgebiet:
Mathematik

DDC Sachgruppe:
Mathematik