97-39
The Linear Ordering Polytope
Preprint series: 97-39, Preprints
- MSC:
- 90C10 Integer programming
Abstract: In this paper we discuss a facial structure of the linear ordering polytope. The facet-defining digraphs M bius ladders are introduced by G.Reinelt [4]. The definition of M bius ladder contains the next condition: If two dicycles C_i and C_j , i < j have a common node then this node belongs either to all dicycles C_i ,...,C_j or to all dicycles C_j,...,C_k,C_1,...,C_i . We show that if this condition of M bius ladder is relaxed then, in general, we do not obtain a facet-defining digraph. Contrary to G.Reinelt [4] we show that digraph Z_4 is not facet-defining. We formulate sufficient conditions for a digraph to be facet-defining. We introduce a new method for generating of facets of the linear ordering polytope by using known ones.
Keywords: Linear ordering polytope, facet, Möbius ladder, generating of facets,acyclic spanning tournament.
Notes: Supported by Gaduiertenstipendium LSA. Submitted to \'Optimization\'.