Zurück zu den Preprints des Jahres 1998


1998-02

On the Relaxation Polytope of the Linear Ordering Problem

by Girlich, E., Nalivaiko, V..


Series: 1998-02, Preprints

MSC:
90C10 Integer programming

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



Keywords:
Linear ordering polytope, relaxation polytope, rotation mapping