Zurück zu den Preprints des Jahres 1997


The Constructive Facet-Generating Methods for the Linear Ordering Polytope

by Girlich, E., Kovalev, M., Nalivaiko, V..

Series: 1997-40, Preprints

90C10 Integer programming

this paper we present two methods (Rotation and Extension) for
generating new facets of the linear ordering polytope by using known facets.
The rotation method generalizes facets induced by digraphs called m-fences and
Möbius ladders introduced by Reinelt (1985), (m; k)-fences introduced by Bolota-
shvily (1986), t-reinforced m-fences introduced by Leung and Lee (1992). We intro-
duce some collections of facets induced by rotation method. Among them there are
facets that coincide with: m-wheel-facets introduced by Reinelt (1985), augmented
m-fences introduced by McLennan (1990) and augmented t-reinforced m-fences in-
troduced by Leung and Lee(1992).
The Extension method generates new facets by connection a Möbius ladder with
a special digraph, and for this new facet-defining digraph we can apply Extension

Linear ordering polytope, facet, Möbius ladder, generating of facets,acyclic spanning tournament.