More facets from fences for linear ordering and acyclic subgraph polytopes

Janny Leung and Jon Lee
Additional contact information
Jon Lee: Yale University and CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1992009, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We present new facets for the linear ordering polytope. These new facets generalize facets induced by sub graphs called fences, introduced by Grotschel, Junger and Reinelt (1985), and augmented fences, introduced by McLennan (1990). One novelty of the facets introduced here is that each sub graph induces not one but a family of facets, which are not generally rank inequalities. Indeed, we provide the smallest known example of a facet-representing inequality for the linear ordering polytope that is not a rank inequality. Gilboa (1990) introduced the diagonal inequalities for the linear ordering polytope, and Fishburn (1991) posed the question of identifying precisely which diagonal inequalities represent facets. We completely resolve Fishburn's question. Some of our results can be transported to the acyclic subgraph polytope. These new facets for the acyclic subgraph polytope are the first ones that are not represented by rank inequalities.

Date: 1992-01-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1992.html (text/html)

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:cor:louvco:1992009

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().