Bernd Perscheid

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

    Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Quadratic Programming Tags ,

    Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which … Read more