Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
Endre Boros, Yves Crama, P. L. Hammer · SIAM Journal on Discrete Mathematics · 1992
In this paper a new lower bound for unconstrained quadratic 0 – 1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron ${\text{S}}^{[3]} $, defined by the constraints of this LP formulation is precisely the first Chvátal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with ${\text{S}}^{[3]} $. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.