Polyhedral Combinatorics

W. R. Pulleyblank
Additional contact information
W. R. Pulleyblank: University of Waterloo, Department of Combinatorics and Optimization

A chapter in Mathematical Programming The State of the Art, 1983, pp 312-345 from Springer

Abstract: Abstract Polyhedral combinatorics deals with the application of various aspects of the theory of polyhedra and linear systems to combinatorics. Over the past thirty years a great many researchers have shown how a large number of polyhedral concepts and results have elegant combinatorial consequences. Here, however, we concentrate our attention on developments over the last ten years. We survey the relationship between linear systems which define a polyhedron and combinatorial min-max theorems obtained via linear programming duality. We discuss two methods of improving these theorems, first by reducing the number of dual variables (facet characterizations) and second, by requiring that dual variables take on integer values (total unimodularity and total dual integrality). One consequence of the ellipsoid algorithm for linear programming has been to show the equivalence of optimization and separation (determining whether or not a given point belongs to a polyhedron, and if not, finding a separating hyperplane). We discuss the theoretical importance of this as well as several instances where in this approach was used to solve successfully “real world” optimization problems (before the development of the ellipsoid method). Finally, we briefly discuss the concepts of adjacency and dimension, both of which recently have been shown to have interesting combinatorial consequences.

Keywords: Travel Salesman Problem; Incidence Vector; Dual Linear Program; Ellipsoid Algorithm; Clique Tree (search for similar items in EconPapers)
Date: 1983
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-642-68874-4_13

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

DOI: 10.1007/978-3-642-68874-4_13

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 ().