CHVATAL CUTS AND ODD CYCLE INEQUALITIES IN QUADRATIC 0 - 1 OPTIMIZATION

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 S[3], defined by the constraints of this LP formulation is precisely the first Chvatal 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 S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.