97-40
The Constructive Facet-Generating Methods for the Linear Ordering Polytope
by Girlich, E. (Magdeburg); Kovalev, M.; Nalivaiko, V.
Preprint series: 97-40, Preprints
- MSC:
- 90C10 Integer programming
Abstract: In 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 Bolotashvily (1986), t-reinforced m-fences introduced by Leung and Lee (1992). We introduce 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 introduced 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.