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.