odd cycle inequalities

A smaller extended formulation for the odd cycle inequalities of the stable set polytope

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Graphs and Matroids Tags , , , ,

    For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more

    The p-median polytope of restricted Y-graphs

  • Mourad Baiou
  • Francisco Barahona
    • Categories Polyhedra Tags , ,

    We further study the effect of odd cycle inequalities in the description of the polytopes associated with the p-median and uncapacitated facility location problems. We show that the obvious integer linear programming formulation together with the odd cycle inequalities completely describe these polytopes for the class of restricted Y-graphs. This extends our results for the … Read more