# zbMATH — the first resource for mathematics

Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization. (English) Zbl 0761.90069
An unconstrained quadratic 0-1 minimization problem is investigated. It is shown that a new lower bound can be computed by solving an LP problem of polynomial size in the number of variables. The polyhedron $$S^{[3]}$$, defined by the constraints of this LP is the first Chvátal closure of the polyhedron, associated with standard linearization procedures.
Reviewer: J.Mitev (Sofia)

##### MSC:
 90C09 Boolean programming 90C20 Quadratic programming 52B12 Special polytopes (linear programming, centrally symmetric, etc.) 90C27 Combinatorial optimization
##### Keywords:
unconstrained quadratic 0-1 minimization; lower bound
Full Text: