# A Cutting Plane Algorithm for the Linear Ordering Problem

Grötschel, Martin and Jünger, Michael and Reinelt, Gerhard
(1984)
*A Cutting Plane Algorithm for the Linear Ordering Problem.*
**Published in: **
Operations Research Vol. 32 (6).
pp. 1195-1220.

## Abstract

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological seriation, minimizingtotal weighted completion time in one-machine scheduling, and aggregation of individualpreferences). In a former paper, we have investigated the facet structure of the 0/1 -polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular,we could triangulate all input-output matrices, of size up to 60 x 60, available to us within acceptable time bounds.

ZAIK Number: | UNSPECIFIED |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 01 Sep 2010 12:39 |

Last Modified: | 04 Jul 2014 09:33 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/818 |