Abstract
LetD n be the complete digraph onn nodes, and letP nLO denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD n (i.e. these are exactly the acyclic tournaments ofD n ). We show that various classes of inequalities define facets ofP nLO , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V.J. Bowman, “Permutation polyhedra”, SIAMJournal on Applied Mathematics 22 (1972) 580–589.
M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness (Freeman, San Francisco, 1979).
M. Grötschel, M. Jünger and G. Reinelt, “On the acyclic subgraph polytope”, this volume, pp. 28–42.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220.
M. Grötschel, M. Jünger and G. Reinelt, “Optimal triangulation of large real-world input-outputmatrices”,Statistische Hefte 25 (1984) 261–295.
B. Korte and W. Oberhofer, “Zwei Algorithmen zur Lösung eines komplexen Reinhenfolgeproblems”,Unternehmensforschung 12 (1968) 217–362.
B. Korte and W. Oberhofer, “Zur Triangulation von Input-Output Matrizen”,Jahrbücher für Nationalökonomie und Statistik 182 (1969) 398–433.
H.W. Lenstra, Jr., “The acyclic subgraph problem”, Report BW26, Mathematisch Centrum (Amsterdam, 1973).
J.F. Mascotorchino and P. Michaud,Optimisation en analyse ordinale des données (Masson, Paris, 1979).
H. Wessels, “Triangulation und Blocktriangulation von Input-Output Tabellen”,Deutsches Institut für Wirtschaftsforschung: Beiträge aur Strukturforschung, Heft 63, Berlin, 1981.
H.P. Young, “On permutations and permutation polytopes”,Mathematical Programming Study 8 (1978) 128–140.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Jünger, M. & Reinelt, G. Facets of the linear ordering polytope. Mathematical Programming 33, 43–60 (1985). https://doi.org/10.1007/BF01582010
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582010