Facet Generating Techniques
A major goal of polyhedral combinatorics is to find classes of essential, i.e. facet inducing, inequalities which describe a combinatorially defined polyhedron P. In general this is a difficult task. We consider the case in which we have knowledge of face
- PDF / 346,540 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 220 Views
Summary. A major goal of polyhedral combinatorics is to find classes of essential, i.e. facet inducing, inequalities which describe a combinatorially defined polyhedron P . In general this is a difficult task. We consider the case in which we have knowledge of facets for a face F of P , and present a general technique for exploiting the close relationship between such polyhedra in order to obtain facets for P from facets of F . We demonstrate the usefulness of this technique by applying it in three instances where this relationship holds, namely the linear ordering polytope and the acyclic subgraph polytope, the asymmetric travelling salesman polytope and the monotone asymmetric travelling salesman polytope, and the symmetric travelling salesman polytope and the two-connected spanning subgraph polytope. In the last case we obtain a class of facet inducing inequalities for the two-connected spanning subgraph polytope by our procedure. This technique has also been applied by Boyd and Hao (1993) to show a class of inequalities is facet inducing for the two edge connected spanning subgraph polytope, by Leung and Lee (1994) to show a class of inequalities is facet inducing for the acyclic subgraph polytope and by Bauer (1997) to show several classes of inequalities are facet inducing for the circuit polytope. The above technique requires that we demonstrate validity of an inequality. We discuss the problem of proving an inequality is valid for the integer hull of a polyhedron, and show that this problem is in NP for classes of polyhedra having bounded Chvátal–Gomory rank. This has the following consequence. Suppose we have an integer programming formulation of the members of an NP-complete class of problems with the property that we can, in polynomial time, show the validity of our defining inequalities. Then there will be problems in the class for which a linear system sufficient to define the integer hull will necessarily contain an inequality of arbitrarily large Chvátal–Gomory rank unless NP = co-NP. Research partially supported by grants from N.S.E.R.C. of Canada.
34
S. Boyd and W.R. Pulleyblank
2.1 Introduction and Notation Polyhedra defined by combinatorial structures are often closely, and sometimes nontrivially, related. In some cases, one polyhedron is a face of another. For example, the Travelling Salesman Polytope is a face of the Two Connected Polytope, as well as a face of the Monotone Travelling Salesman Polytope and the Graphical Travelling Salesman Polytope. Given a polyhedron P of interest, a major goal of polyhedral combinatorics is to find classes of essential, i.e. facet inducing inequalities which describe P . In general, finding such classes of inequalities is a difficult task, as is proving that these inequalities are facet inducing. Thus if we know of any polyhedra related to P for which facet inducing inequalities are known, it is desirable to exploit the connections between P and these related polyhedra in order to obtain facet inducing inequalities for P . In this paper, we consider the s
Data Loading...
