CONES OF MATRICES AND SET-FUNCTIONS AND 0–1 OPTIMIZATION

CONES OF MATRICES AND SET-FUNCTIONS AND 0–1 OPTIMIZATION

Vol. 1, No. 2, pp. 166-190, May 1991 | L. LOVÁSZ† AND A. SCHRIJVER‡
The paper by László Lovász and Alexander Schrijver introduces a method to represent polyhedra as projections of higher-dimensional polyhedra, which is particularly useful in polyhedral combinatorics. The method involves constructing higher-dimensional polyhedra or convex sets whose projection approximates the convex hull of 0-1 valued solutions of a system of linear inequalities. A key feature of these approximations is that any linear objective function can be optimized over them in polynomial time. The authors apply this method to the vertex packing polytope, obtaining a sequence of systems of inequalities that include clique, odd hole, odd antihole, wheel, and orthogonality constraints. For perfect graphs, this sequence gives the vertex packing polytope, and for various classes of graphs, including t-perfect graphs, it results in the stable set polytope being the projection of a polytope with a polynomial number of facets. The paper also discusses an extension of the method that connects with certain submodular functions and the Möbius function of a lattice. The authors provide a general procedure to create such liftings, extending the method of Grötschel, Lovász, and Schrijver for finding maximum stable sets in perfect graphs to general 0-1 programs. They represent feasible subsets not by their incidence vectors but by matrices, which squares the number of variables but allows for more powerful linear constraints. The method is closely related to recent work by Sherali and Adams on relaxations of 0-1 optimization problems and to the work of Pemantle, Propp, and Ullman on tensor powers of linear programs. The paper includes detailed proofs and examples, demonstrating the effectiveness of the method in various combinatorial optimization problems, such as the stable set problem. It also explores the algorithmic aspects of the constructions, showing that the weak separation problem for the projected cones can be solved in polynomial time.The paper by László Lovász and Alexander Schrijver introduces a method to represent polyhedra as projections of higher-dimensional polyhedra, which is particularly useful in polyhedral combinatorics. The method involves constructing higher-dimensional polyhedra or convex sets whose projection approximates the convex hull of 0-1 valued solutions of a system of linear inequalities. A key feature of these approximations is that any linear objective function can be optimized over them in polynomial time. The authors apply this method to the vertex packing polytope, obtaining a sequence of systems of inequalities that include clique, odd hole, odd antihole, wheel, and orthogonality constraints. For perfect graphs, this sequence gives the vertex packing polytope, and for various classes of graphs, including t-perfect graphs, it results in the stable set polytope being the projection of a polytope with a polynomial number of facets. The paper also discusses an extension of the method that connects with certain submodular functions and the Möbius function of a lattice. The authors provide a general procedure to create such liftings, extending the method of Grötschel, Lovász, and Schrijver for finding maximum stable sets in perfect graphs to general 0-1 programs. They represent feasible subsets not by their incidence vectors but by matrices, which squares the number of variables but allows for more powerful linear constraints. The method is closely related to recent work by Sherali and Adams on relaxations of 0-1 optimization problems and to the work of Pemantle, Propp, and Ullman on tensor powers of linear programs. The paper includes detailed proofs and examples, demonstrating the effectiveness of the method in various combinatorial optimization problems, such as the stable set problem. It also explores the algorithmic aspects of the constructions, showing that the weak separation problem for the projected cones can be solved in polynomial time.
Reach us at info@study.space
[slides and audio] Cones of Matrices and Set-Functions and 0-1 Optimization