98-02
On the Relaxation Polytope of the Linear Ordering Problem
Preprint series: 98-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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.