# zbMATH — the first resource for mathematics

The Boolean quadratic polytope: Some characteristics, facets and relatives. (English) Zbl 0675.90056
Summary: We study unconstrained quadratic zero-one programming problems having n variables from a polyhedral point of view by considering the Boolean quadric polytope $$QP^ n$$ in $$n(n+1)/2$$ dimensions that results from the linearization of the quadratic form. We show that $$QP^ n$$ has a diameter of one, descriptively identify three families of facets of $$QP^ n$$ and show that $$QP^ n$$ is symmetric in the sense that all facets of $$QP^ n$$ can be obtained from those that contain the origin by way of a mapping. The naive linear programming relaxation $$QP^ n_{LP}$$ of $$QP^ n$$ is shown to possess the Trubin-property and its extreme points are shown to be $$\{0,1/2,1\}$$-valued. Furthermore, $$O(n^ 3)$$ facet-defining inequalities of $$QP^ n$$ suffice to cut off all fractional vertices of $$QP^ n_{LP}$$, whereas the family of facets described by us has at least $$O(3^ n)$$ members. The problem is also studied for sparse quadratic forms (i.e. when several or many coefficients are zero) and conditions are given for the previous results to carry over to this case. Polynomially solvable problem instances are discussed and it is shown that the known polynomiality result for the maximization of nonnegative quadratic forms can be obtained by simply rounding the solution to the linear programming relaxation. In the case that the graph induced by the nonzero coefficients of the quadratic form is series-parallel, a complete linear description of the associated Boolean quadric polytope is given. The relationship of the Boolean quadric polytope associated to sparse quadratic forms with the vertex- packing polytope is discussed as well.

##### MSC:
 90C09 Boolean programming 90C20 Quadratic programming 52Bxx Polytopes and polyhedra 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 68Q25 Analysis of algorithms and problem complexity 90C05 Linear programming
Full Text: