×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Balas, ”Exténsion de l’algorithme additif à la programmation en nombres entiers et à la programmation non linéaire,”C.R. Acad. Sci. Paris. 258 (1967) 5136–5139. · Zbl 0208.45705
[2] E. Balas and J. Mazzola, ”Nonlinear 0–1 programming: Parts I & II,”Mathematical Programming 30 (1984) 1–45. · Zbl 0553.90067
[3] E. Balas and M. Padberg, ”On the set covering problem,”Operations Research 20 (1972) 1152–1161. · Zbl 0254.90035
[4] E. Balas and M. Padberg, ”Set partitioning: A survey,”SIAM Review 18 (1976) 710–760. · Zbl 0347.90064
[5] E. Balas and W. Pulleyblank, ”The perfectly matchable subgraph polytope of a bipartite graph,”Networks 13 (1983) 495–516. · Zbl 0525.90069
[6] M. Balinski, ”On maximum matching, minimum covering and their connections,” in: H. Kuhn (ed.),Proceedings of the Princeton Symposium on Mathematical Programming (Princeton U. Press, Princeton, New Jersey, 1970a) pp. 303–312. · Zbl 0228.05122
[7] M. Balinski, ”On a selection problem,”Management Science 17 (1970b) 230–231. · Zbl 0203.52506
[8] F. Barahona, ”A solvable case of quadratic 0–1 programming,”Discrete Applied Mathematics 13 (1986) 23–26. · Zbl 0597.90059
[9] F. Barahona, M. Grötschel and R. Mahjoub, ”Facets of the bipartite subgraph polytope,”Mathematics of Operations Research 10 (1985) 340–358. · Zbl 0578.05056
[10] F. Barahona, M. Jünger and G. Reinelt, ”Experiments in quadratic 0–1 programming,” Report no. 7, Institut für Mathematick, Universität Augsburg, November 1987. · Zbl 0677.90046
[11] F. Barahona and R. Mahjoub, ”On the cut polytope,”Mathematical Programming 36 (1986) 157–173. · Zbl 0616.90058
[12] C. Berge,Graphs and Hypergraphs (North-Holland, Amsterdam, 1973). · Zbl 0254.05101
[13] M. Boulala and J. Uhry, ”Polytope des indépendants d’un graphe série-parallèle,”Discrete Mathematics 7 (1979) 225–243. · Zbl 0449.05065
[14] P. Camion, ”Characterisation of totally unimodular matrices,”Proceedings American Mathematical Society 6 (1965) 1068–1073. · Zbl 0134.25201
[15] V. Chvátal, ”On certain polytopes associated with graphs,” Centre de Recherches Mathématiques-238, Université de Montreal, October 1972. · Zbl 0277.05139
[16] V. Chvátal, ”On certain polytopes associated with graphs,”Journal of Combinatorial Theory B 18 (1975) 138–154. · Zbl 0277.05139
[17] M. Conforti, M.R. Rao and A. Sassano, ”The equipartition polytope: Parts I & II,” R. 194/195, IASI-CNR, Roma (Italy), October 1987. · Zbl 0718.90093
[18] R. Fortet, ”L’algèbre de Boole et ses applications en recherche opérationelle,”Cahiers du Centre d’Etudes de Recherche Opérationelle 1 (1959) 5–36. · Zbl 0093.32704
[19] R. Fortet, ”Applications de l’algèbre de Boole en recherche opérationelle,”Revue Francaise de Recherche Opérationelle 4 (1960) 17–26. · Zbl 0109.38201
[20] E. Girlich and M. Kowaljow,Nichtlineare Diskrete Optimierung (Akademie-Verlag, Berlin, 1981). · Zbl 0478.49001
[21] M. Grötschel, L. Lovasz and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–191. · Zbl 0492.90056
[22] M. Grötschel, L. Lovasz and A. Schrijver, ”Polynomial algorithms for perfect graphs,”Annals of Discrete Mathematics 21 (1984) 325–356.
[23] M. Grötschel and Y. Wakabayashi, ”Facets of the clique-partitioning polytope,” Report no. 6, Institut für Mathematik, Universität Augsburg, June 1987. · Zbl 0715.90092
[24] P. Hammer (Ivanescu), ”Some network flow problems solved with pseudo-boolean programming,”Operations Research 13 (1965) 388–399. · Zbl 0132.13804
[25] P. Hammer (Ivanescu) and Y. Rosenberg, ”Application of pseudo-boolean programming to the theory of graphs,”Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 3 (1967) 163–176. · Zbl 0141.35801
[26] P. Hammer, P. Hansen and B. Simeone, ”Roof duality, complementation and persistency in quadratic 0–1 programming,”Mathematical Programming 28 (1984) 121–155. · Zbl 0574.90066
[27] P. Hansen, ”Methods of nonlinear 0–1 programming,”Annals of Discrete Mathematics 5 (1979) 53–70. · Zbl 0426.90063
[28] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[29] L. Khachiyan, ”A polynomial algorithm in linear programming,”Soviet Math. Doklady 20 (1979) 191–194. · Zbl 0414.90086
[30] E. Lawler, ”The quadratic assignment problem,”Management Science 9 (1963) 586–599. · Zbl 0995.90579
[31] R. Mahjoub, ”On the stable set polytope of a series-parallel graph,”Mathematical Programming 40 (1988) 53–57. · Zbl 0652.05029
[32] G. Nemhauser and L. Trotter, ”Vertex packings: Structural properties and algorithms,”Mathematical Programming 8 (1975) 232–248. · Zbl 0314.90059
[33] M. Padberg, ”Essays in integer programming,” PhD thesis, GSIA, Carnegie-Mellon University, Pittsburgh, April 1971.
[34] M. Padberg, ”On the facial structure of set packing polyhedra,” Report I-13, International Institute of Management, Berlin (West), April 1972a. · Zbl 0272.90041
[35] M. Padberg, ”On the adjacent vertices cut,” International Institute of Management, Berlin (West), May 1972b.
[36] M. Padberg, ”On the facial structure of set packing polyhedra,”Mathematical Programming 5 (1973) 199–216. · Zbl 0272.90041
[37] M. Padberg, ”A note on zero–one programmin,”Operations Research 23 (1975) 833–837. · Zbl 0311.90053
[38] M. Padberg, ”Almost integral polyhedra related to certain combinatorial optimization problems,”Linear Algebra and Its Applications 15 (1956) 69–88. · Zbl 0362.90077
[39] M. Padberg, ”On the complexity of set packing polyhedra,”Annals of Discrete Mathematics 1 (1977) 421–434. · Zbl 0399.05017
[40] M. Padberg, ”Zero–one decision problems,” GBA-Report No. 76-29, April 1976, New York University. Published (in German) in: M. Beckmann et al. (eds.),Handwörterbuch der Mathematischen Wirtschafts-wissenschaften (Gabler-Verlag, Wiesbaden, 1978) pp. 187–229.
[41] M. Padberg, ”Covering, packing and knapsack problems,”Annals of Discrete Mathematics 4 (1979) 265–287. · Zbl 0407.90056
[42] M. Padberg, ”Total unimodularity and the Euler-subgraph problem,”Operations Research Letters 7 (1988) 173–179. · Zbl 0652.90075
[43] M. Padberg and M.R. Rao, ”The travelling salesman problem and a class of polyhedra of diameter two,”Mathematical Programming 7 (1974) 32–45. · Zbl 0318.90042
[44] M. Padberg and M.R. Rao, ”The Russian method for linear inequalities III: Bounded integer programming,” July 1981. Report 81-39, GBA, New York University, New York.
[45] M. Padberg and G. Rinaldi, ”Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut,”Operations Research Letters 6 (1987) 1–7. · Zbl 0618.90082
[46] J. Picard and D. Ratliff, ”Minimum cuts and related problems,”Networks 5 (1975) 357–370. · Zbl 0325.90047
[47] J. Rhys, ”A selection problem of shared fixed costs and networks,”Management Science 7 (1970) 200–207. · Zbl 0203.52505
[48] L. Trotter, ”Solution characteristics and algorithms for vertex packings,” PhD thesis, Dept. for Operations Research, Cornell University, Ithaca, NY, January 1973.
[49] L. Trotter, ”A class of facet-producing graphs for vertex packing polytopes,”Discrete Mathematics 12 (1975) 373–391. · Zbl 0314.05111
[50] V. Trubin, ”On a method of solution of integer linear programming problems of a special kind,”Soviet Mathematics Doklady 10 (1969) 1544–1546. · Zbl 0209.51201
[51] A. Williams, ”Quadratic 0–1 programming using the roof dual with computational results,” RUTCOR Report 8-85, Rutgers University, New Brunswick, NJ, 1985.
[52] L. Wolsey, ”Further facet generating procedures for vertex packing polytopes,”Mathematical Programming 11 (1976) 158–163. · Zbl 0348.90148
[53] V. Yemelichev, M. Kovalev and M. Kraftsov,Polytopes, Graphs and Optimization (Cambridge University Press, Cambridge, 1985).
[54] E. Zemel, ”Lifting the facets of zero–one polytopes,”Mathematical Programming 15 (1978) 268–277. · Zbl 0428.90042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.