On the Relaxation Polytope of the Linear Ordering Problem

by Girlich, E.; Nalivaiko, V.


Preprint series: 98-02, Preprints

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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster