Facet Generating Techniques

Sylvia Boyd () and William R. Pulleyblank ()
Additional contact information
Sylvia Boyd: University of Ottawa, School of Information Technology and Engineering
William R. Pulleyblank: IBM Global Business Services, Center for Business Optimization

Chapter 2 in Research Trends in Combinatorial Optimization, 2009, pp 33-55 from Springer

Abstract: 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.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_2

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().