ISSN:
1436-4646
Schlagwort(e):
Unconstrained zero–one quadratic programming
;
polyhedral combinatorics
;
facets
;
polytopes
;
vertex-packing
;
series-parallel graphs
;
polynomial solvability
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract We study unconstrained quadratic zero–one programming problems havingn variables from a polyhedral point of view by considering the Boolean quadric polytope QP n inn(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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01589101
Permalink
