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

@article{citeulike:2594388, 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\"{o}bius function of a lattice.}, author = {Lov\'{a}sz}, citeulike-article-id = {2594388}, doi = {10.1137/0801013}, journal = {SIAM Journal on Optimization}, keywords = {algebra, algorithms, optimization}, number = {2}, pages = {166--190}, posted-at = {2008-03-26 14:22:54}, priority = {2}, title = {Cones of Matrices and Set-Functions and 0–1 Optimization}, url = {http://dx.doi.org/10.1137/0801013}, volume = {1}, year = {1991} }

TY - JOUR ID - citeulike:2594388 L3 - citeulike-article-id:2594388 TI - Cones of Matrices and Set-Functions and 0–1 Optimization JF - SIAM Journal on Optimization VL - 1 IS - 2 SP - 166 EP - 190 N2 - 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. KW - algebra KW - algorithms KW - optimization AU - Lovász PY - 1991/// UR - http://dx.doi.org/10.1137/0801013 ER -