Facets of the linear ordering polytope
作者： Martin Grötschel , Michael Jünger , Gerhard Reinelt
DOI: 10.1007/BF01582010
关键词:
摘要: LetD n be the complete digraph onn nodes, and letP LO denote convex hull of all incidence vectors arc sets linear orderings nodes ofD (i.e. these are exactly acyclic tournaments ). We show that various classes inequalities define facets ofP , e.g. 3-dicycle inequalities, simplek-fence Mobius ladder we discuss use in cutting plane approaches to triangulation problem input-output matrices, i.e. solution permutation resp. ordering problems.
springer.com
sci-hub.se 参考文章(10)
H. P. Young, On permutations and permutation polytopes Mathematical Programming Studies. pp. 128- 140 ,(1978) , 10.1007/BFB0121198
J. F. Marcotorchino, P. Michaud, Optimisation en analyse ordinale des données Masson. ,(1979)
H.W. Lenstra, The acyclic subgraph problem Stichting Mathematisch Centrum. Mathematische Besliskunde. pp. 1- 45 ,(1973)
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Martin Grötschel, Michael Jünger, Gerhard Reinelt, On the acyclic subgraph polytope Mathematical Programming. ,vol. 33, pp. 28- 42 ,(1985) , 10.1007/BF01582009
B. Korte, W. Oberhofer, Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems Unternehmensforschung Operations Research - Recherche Opérationnelle. ,vol. 12, pp. 217- 231 ,(1968) , 10.1007/BF01918332
Martin Grötschel, Michael Jünger, Gerhard Reinelt, A Cutting Plane Algorithm for the Linear Ordering Problem Operations Research. ,vol. 32, pp. 1195- 1220 ,(1984) , 10.1287/OPRE.32.6.1195
M. Grötschel, M. Jünger, G. Reinelt, Optimal triangulation of large real world input-output matrices Statistische Hefte. ,vol. 25, pp. 261- 295 ,(1983) , 10.1007/BF02932410
Bernhard Körte, Walter Oberhofer, Zur Triangulation von Input-Output-Matrizen Jahrbucher Fur Nationalokonomie Und Statistik. ,vol. 182, pp. 398- 433 ,(1968) , 10.1515/JBNST-1968-0125