A Cutting Plane Algorithm for the Linear Ordering Problem

Martin Grötschel, Michael Jünger and Gerhard Reinelt
Additional contact information
Martin Grötschel: Universitat Augsburg, Augsburg, West Germany
Michael Jünger: Universitat Augsburg, Augsburg, West Germany
Gerhard Reinelt: Universitat Augsburg, Augsburg, West Germany

Operations Research, 1984, vol. 32, issue 6, 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 senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). 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 × 60, available to us within acceptable time bounds.

Keywords: 133 triangulation of input-output tables; 432 polyhedral combinatorics; 625 cutting plane methods (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.6.1195 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:6:p:1195-1220

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().