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. We develop a general method 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, we obtain a sequence of systems of inequalities, such that already the first system 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. We also discuss an extension of the method, which establishes a connection with certain submodular functions and the Möbius function of a lattice. 1980 Mathematics subject classification: 05C35, 90C10, 90C27. Key words and phrases: polyhedron, cone, vertex packing polytope, perfect graph, Möbius function. 1 One of the most important methods in combinatorial optimization is to represent each feasible solution of the problem by a 0-1 vector (usually the incidence vector of the appropriate set), and then describe the convex hull K of the solutions by a system of linear inequalities. In the nicest cases (e.g. in the case of the bipartite matching problem) we obtain a system that has polynomial size (measured in the natural "size" n of the problem). In such a case, we can compute the maximum of any linear objective function in polynomial time by solving a linear program. In other cases, however, the convex hull of feasible solutions has exponentially many facets and so can only be described by a linear program of exponential size. For many combinatorial optimization problems (including those solvable in polynomial time), this exponentially large set of linear inequalities is still "nice" in one sense or another. We mention two possible notions of "niceness": -Given an inequality in the system, there is a polynomial size certificate of the fact that it is valid for K. If this is the case, the problem of determining whether a given vector in K is in the complexity class co-NP. -There is a polynomial time separation algorithm for the system; that is, given a vector, we can check in polynomial time whether it satisfies the system, and if not, we can find an inequality in the system that is violated. It follows then from general results on the ellipsoid method (see Grötschel, Lovász and Schrijver 1988) that every linear objective function can be optimized over K in polynomial time. Many important theorems in combinatorial optimization provide such "nice" descriptions of polyhedra. Important examples of polyhedra with "nice" descriptions are matching polyhedra, matroid polyhedra, stable set polyhedra for perfect graphs etc. On the other hand, stable set polyhedra in general, or travelling salesman polyhedra, are not known to have "nice" descriptions (and probably don't have any). Typically, to find such a "nice" description and to prove its correctness, one needs ad hoc methods depending on the combinatorial structure. However, one can mention two general ideas that can help in obtaining such linear descriptions: -Gomory-Chvátal cuts. Let P be a polytope with integral vertices. Assume that we have already found a system of linear inequalities valid for P whose integral solutions are precisely the integral vectors in P . The solution set of this system is a polytope K containing P which will in general be larger than P . We can generate further linear inequalities valid for P (but not necessarily for K) as follows. Given a linear inequality valid for K, where the a i are integers, the inequality i a i x i ≤ α is still valid for P but may eliminate some part of K. Gomory (1963) used a special version of this construction in his integer programming algorithm. If we take all inequalities obtainable this way, they define a polytope K with P ⊆ K ⊂ K. Repeating this with K in place of K we obtain K etc. Chvátal (1973) proved that in a finite number of steps, we obtain the polytope P itself. Unfortunately, the number of steps needed may be very large; it depends not only on the dimension but also on the coefficients of the system we start with. Another trouble with this procedure is that there is no efficient way known to implement it algorithmically. In particular, even if we know how to optimize a linear objective function over K in polynomial time (say, K is given by an explicit, polynomial-size linear program), and K = P , we know of no general method to optimize a linear objective function over P in polynomial time. -Projection representation (new variables). This method has received much attention lately. The idea is that a projection of a polytope may have more facets than the polytope itself. This remark suggests that even if P has exponentially many facets, we may be able to represent it as the projection of a polytope Q in higher (but still polynomial) dimension, having only a polynomial number of facets. Among others, Ball, Liu and Pulleyblank (1987) , Maculan (1987) , Pulleyblank (1983, 1987), Barahona and Mahjoub (1987), Cameron and Edmonds (1988) have provided non-trivial examples of such a representation. It is easy to see that such a representation can be used to optimize linear objective functions over P in polynomial time. In the negative direction, Yannakakis (1988) proved that the Travelling Salesman polytope and the Matching Polytope of complete graphs cannot be represented this way, assuming that the representation is "canonical". (Let P ⊆ IR n and P ⊆ IR m be two polytopes. We say that a projection representation π : P → P is canonical if the group Γ of isometries of IR n preserving P has an action as isometries of IR m preserving P so that the projection commutes with these actions. Such a representation is obtained e.g. when new variables are introduced in a "canonical" way -in the case of the travelling salesman polytope, this could mean variables assigned to edges or certain other subgraphs, and constraints on these new variables are derived from local properties. If we have to start with a reference orientation, or with specifying a root, then the representation obtained will not be canonical.) No negative results seem to be known without this symmetry assumption. One way to view our results is that we provide a general procedure to create such liftings. The idea is to extend the method of Grötschel, Lovász and Schrijver (1981) for finding maximum stable sets in perfect graphs to general 0-1 programs. We represent a feasible subset not by its incidence vector v but by the matrix vv T . This squares the number of variables, but in return we obtain two new powerful ways to write down linear constraints. Projecting back to the "usual" space, we obtain a procedure somewhat 3 similar to the Gomory-Chvátal procedure: it "cuts down" a convex set K to a new convex set K so that all 0-1 solutions are preserved. In contrast to the GomoryChvátal cuts, however, any subroutine to optimize a linear objective function over K can be used to optimize a linear objective function over K . Moreover, repeating the procedure at most n times, we obtain the convex hull P of 0-1 vectors in K. Our method is closely related to recent work of Sherali and Adams (1988) . They introduce new variables for products of the original ones and characterize the convex hull, in this high-dimensional space, of vectors associated with 0-1 solutions of the original problem. In this way they obtain a sequence of relaxations of the 0-1 optimization problem, the first of which is essentially the N operator introduced in section 1 below. Further members of the two sequences of relaxations are different, but closely related; some of our results in section 3, in particular, formula (6) and Theorem 3.3, follow directly from their work. The method is also related to (but different from) the recent work of Pemantle, Propp and Ullman (1989) on the tensor powers of linear programs. In section 1, we describe the method in general, and prove its basic properties. Section 2 contains applications to the vertex packing problem, one of the best studied combinatorial optimization problems. It will turn out that our method gives in one step almost all of the known classes of facets of the vertex packing polytope. It will follow in particular that if a graph has the property that its stable set polytope is described by the clique, odd hole and odd antihole constraints, then its maximum stable set can be found in polynomial time. In section 3 we put these results in a wider context, by raising the dimension even higher. We introduce exponentially many new variables; in this high-dimensional space, rather simple and elegant polyhedral results can be obtained. The main part of the work is to "push down" the inequalities to a low dimension, and to carry out the algorithms using only a polynomial number of variables and constraints. It will turn out that the methods in section 1, as well as other constructions like TH(G) as described in Grötschel, Lovász and Schrijver (1986, 1988) follow in a natural way. Acknowledgement. The first author is grateful to the Department of Combinatorics and Optimization of the University of Waterloo for its hospitality while this paper was written. Discussions with Mike Saks and Bill Pulleyblank on the topic of the paper were most stimulating.
The matching polytope was first studied in the lift-andproject context by Lovász and Schrijver REF , who posed the problem of determining the rank (i.e., the minimum number of rounds until the integer polytope is reached) for complete graphs Kn.
Cones of matrices and set-functions and 0-1 optimization
SIAM JOURNAL ON OPTIMIZATION
Computer Science Mathematics