Zurück zu den Preprints des Jahres 1997


1997-40

The Constructive Facet-Generating Methods for the Linear Ordering Polytope

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


Series: 1997-40, Preprints

MSC:
90C10 Integer programming

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

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