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

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

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