The Boolean quadratic polytope: Some characteristics, facets and relatives

The paper studies unconstrained quadratic zero-one programming problems having n variables from a polyhedral point of view by considering the Boolean quadric polytope in dimensions that results from the linearization of the quadratic form. It shows that has a diameter of one, descriptively identify three families of facets of and shows that is symmetric in the sense that all facets of can be obtained from those that contain the origin by way of a mapping. The naive linear programming relaxation of is shown to possess the Trubin-property and its extreme points are shown to be -valued. Furthermore, O(n ³) facet-defining inequalities of QP ⁿ suffice to cut off all fractional vertices of , whereas the family of facets described by the paper has at least O(3 ⁿ ) 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.