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.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
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