Zurück zu den Preprints des Jahres 1998


On the Relaxation Polytope of the Linear Ordering Problem

by Girlich, E., Nalivaiko, V..

Series: 1998-02, Preprints

90C10 Integer programming

In this paper we consider the relaxation polytope $\Bn$
of the linear ordering polytope $\Pn$.
The polytope $\Bn$ is sometimes called Bowman's polytope and $\Bn$ is
3-dicycle relaxation of $\Pn$. We show that non-integer vertices of $\Bn$
have only the coordinates: 1, 0, 1/2.
It can help us to develop new effective heuristic algorithms for solving
linear ordering problems.

Linear ordering polytope, relaxation polytope, rotation mapping