research-article

Cones of Matrices and Set-Functions and 0–1 Optimization

Authors:

A. SchrijverAuthors Info & Claims

SIAM Journal on Optimization, Volume 1, Issue 2

Pages 166 - 190

https://doi.org/10.1137/0801013

Published: 01 May 1991 Publication History

Abstract

It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron, is a powerful tool in polyhedral combinatorics. A general method is developed to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0–1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.

In the special case of the vertex packing polytope, a sequence of systems of inequalities is obtained such that the first system already includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, this first system gives the vertex packing polytope. For various classes of graphs, including t-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets.

An extension of the method is also discussed which establishes a connection with certain submodular functions and the Möbius function of a lattice.

References

[1]

E. Balas, W. R. Pulleyblank, The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13 (1983), 495–516

[2]

E. Balas, W. R. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary graph, Combinatorica, 9 (1989), 321–337

[3]

M. O. Ball, W. Liu, W. R. Pulleyblank, B. Tulkens, H. Tulkens, Two-terminal Steiner tree polyhedraContributions to operations research and economics (Louvain-la-Neuve, 1987), MIT Press, Cambridge, MA, 1989, 251–284

[4]

F. Barahona, Reducing matching to polynomial size linear programming, Res. Report, CORR 88-51, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, 1988

[5]

F. Barahona, A. R. Mahjoub, Compositions of graphs and polyhedra II: Stable sets, Res. Report, 87464-OR, Institut für Operations Research, Universität Bonn, Bonn, FRG, 1987

[6]

Kathie Cameron, Jack Edmonds, Coflow polyhedra, Discrete Math., 101 (1992), 1–21

Digital Library

[7]

S. Ceria, 1989, personal communication

[8]

V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4 (1973), 305–337

Digital Library

[9]

V. Chvátal, On certain polytopes associated with graphs, J. Combinatorial Theory Ser. B, 18 (1975), 138–154

[10]

Jack Edmonds, Maximum matching and a polyhedron with $0,1$-vertices, J. Res. Nat. Bur. Standards Sect. B, 69B (1965), 125–130

[11]

Ralph E. Gomory, R. Graves, P. Wolfe, An algorithm for integer solutions to linear programsRecent advances in mathematical programming, McGraw-Hill, New York, 1963, 269–302

[12]

M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169–197

[13]

M. Grötschel, L. Lovász, A. Schrijver, Relaxations of vertex packing, J. Combin. Theory Ser. B, 40 (1986), 330–343

Digital Library

[14]

Martin Grötschel, László Lovász, Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics: Study and Research Texts, Vol. 2, Springer-Verlag, Berlin, 1988xii+362, New York

[15]

Bernt Lindström, Determinants on semilattices, Proc. Amer. Math. Soc., 20 (1969), 207–208

[16]

W. Liu, Ph.D. Thesis, Extended formulations and polyhedral projection, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, 1988

[17]

L. Lovász, Combinatorial problems and exercises, North-Holland Publishing Co., Amsterdam, 1979, 551–, Akadémiai Kiadó, Budapest, Hungary; the Netherlands

[18]

L. Lovász, M. D. Plummer, Matching theory, North-Holland Mathematics Studies, Vol. 121, North-Holland Publishing Co., Amsterdam, 1986xxvii+544, Elsevier, the Netherlands

[19]

N. Maculan, The Steiner problem in graphs, Ann Discrete Math., 31 (1987), 185–222

[20]

Robin Pemantle, James Propp, Daniel Ullman, On tensor powers of integer programs, SIAM J. Discrete Math., 5 (1992), 127–143

Digital Library

[21]

Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2 (1964), 340–368 (1964)

[22]

Hanif D. Sherali, Warren P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), 411–430

Digital Library

[23]

Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986xiv+306

Digital Library

[24]

Herbert S. Wilf, Hadamard determinants, Möbius functions, and the chromatic number of a graph, Bull. Amer. Math. Soc., 74 (1968), 960–964

[25]

R. J. Wilson, P. Erdös, A. Rényi, V. T. Sós, The Selberg sieve for a latticeCombinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969), Vol. 4, North-Holland, Amsterdam, 1970, 1141–1149, Coll. Math. Soc. János Bolyai

[26]

M. Yannakakis, Expressing combinatorial optimization problems by linear programs, Proc. 29th IEEE Symposium on Foundations of Computer Science, White Plains, NY, 1988, 223–228

Cited By

Bianchi SEscalante MNasini GWagler A(2023)Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphsDiscrete Applied Mathematics10.1016/j.dam.2023.01.012332:C(70-86)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.01.012
Castro-Silva Dde Oliveira Filho FSlot LVallentin F(2023)A Recursive Theta Body for HypergraphsCombinatorica10.1007/s00493-023-00040-943:5(909-938)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/s00493-023-00040-9
Gutekunst SWilliamson D(2022)Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality GapsMathematics of Operations Research10.1287/moor.2020.110047:1(1-28)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1287/moor.2020.1100
Show More Cited By

Index Terms

Cones of Matrices and Set-Functions and 0–1 Optimization
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
  2. Mathematical analysis
    1. Mathematical optimization
    2. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube

Gomory’s and Chvátal’s cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvátal rank of the polyhedron is the number of rounds needed to obtain all valid inequalities. It is ...
Perfect graphs and norms

For a given undirected graphG=(V, ź) withn vertices we define four norms on źn, namely[Figure not available: see fulltext.], where ź (resp.[Figure not available: see fulltext.]) stands for the family of all maximal cliques inG (resp. $$\tilde G$$ , the ...
Spectrahedral cones generated by rank 1 matrices

Let $$\mathcal{S}_+^n \subset \mathcal{S}^n$$S+n Sn be the cone of positive semi-definite matrices as a subset of the vector space of real symmetric $$n \times n$$n n matrices. The intersection of $$\mathcal{S}_+^n$$S+n with a linear subspace of $$\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 1, Issue 2

May 1991

142 pages

ISSN:1052-6234

DOI:10.1137/sjope8.1991.1.issue-2

Issue’s Table of Contents

Copyright © 1991 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 1991

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bianchi SEscalante MNasini GWagler A(2023)Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphsDiscrete Applied Mathematics10.1016/j.dam.2023.01.012332:C(70-86)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.01.012
Castro-Silva Dde Oliveira Filho FSlot LVallentin F(2023)A Recursive Theta Body for HypergraphsCombinatorica10.1007/s00493-023-00040-943:5(909-938)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/s00493-023-00040-9
Gutekunst SWilliamson D(2022)Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality GapsMathematics of Operations Research10.1287/moor.2020.110047:1(1-28)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1287/moor.2020.1100
Niu YGlowinski R(2022)Discrete Dynamical System Approaches for Boolean Polynomial OptimizationJournal of Scientific Computing10.1007/s10915-022-01882-z92:2Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10915-022-01882-z
Hu HLi XWu J(2022)A note on the SDP relaxation of the minimum cut problemJournal of Global Optimization10.1007/s10898-022-01235-y87:2-4(857-876)Online publication date: 29-Sep-2022
https://dl.acm.org/doi/10.1007/s10898-022-01235-y
Slot LLaurent M(2022)Sum-of-squares hierarchies for binary polynomial optimizationMathematical Programming: Series A and B10.1007/s10107-021-01745-9197:2(621-660)Online publication date: 7-Jan-2022
https://dl.acm.org/doi/10.1007/s10107-021-01745-9
Bärmann ASchneider O(2022)Set characterizations and convex extensions for geometric convex-hull proofsMathematical Programming: Series A and B10.1007/s10107-021-01705-3195:1-2(475-515)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s10107-021-01705-3
Vervier KMahé PD’Aspremont AVeyrieras JVert J(2022)On Learning Matrices with Orthogonal Columns or Disjoint SupportsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44845-8_18(274-289)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44845-8_18
Bazzi AFiorini SPokutta SSvensson O(2019)No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛMathematics of Operations Research10.1287/moor.2017.091844:1(147-172)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1287/moor.2017.0918
Gaar ERendl F(2019)A Bundle Approach for SDPs with Exact Subgraph ConstraintsInteger Programming and Combinatorial Optimization10.1007/978-3-030-17953-3_16(205-218)Online publication date: 22-May-2019
https://dl.acm.org/doi/10.1007/978-3-030-17953-3_16
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents