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)

90C09 Boolean programming
90C20 Quadratic programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C27 Combinatorial optimization
PDF BibTeX Cite
Full Text: DOI