Zurück zu den Preprints des Jahres 1997


1997-39

The Linear Ordering Polytope

by Nalivaiko, V..


Series: 1997-39, Preprints

MSC:
90C10 Integer programming

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