×

Facets of the linear ordering polytope. (English) Zbl 0577.05035

Summary: Let \(D_ n\) be the complete digraph on n nodes, and let \(P^ n_{LO}\) denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes of \(D_ n\) (i.e. these are exactly the acyclic tournaments of \(D_ n)\). We show that various classes of inequalities define facets of \(P^ n_{LO}\), e.g. the 3-dicycle inequalities, the simple k-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.

MSC:

05C20 Directed graphs (digraphs), tournaments
52Bxx Polytopes and polyhedra
90C10 Integer programming

Citations:

Zbl 0577.05034
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V.J. Bowman, ”Permutation polyhedra”, SIAMJournal on Applied Mathematics 22 (1972) 580–589. · Zbl 0246.90030 · doi:10.1137/0122054
[2] M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[3] M. Grötschel, M. Jünger and G. Reinelt, ”On the acyclic subgraph polytope”, this volume, pp. 28–42. · Zbl 0577.05034
[4] M. Grötschel, M. Jünger and G. Reinelt, ”A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220. · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[5] M. Grötschel, M. Jünger and G. Reinelt, ”Optimal triangulation of large real-world input-outputmatrices”,Statistische Hefte 25 (1984) 261–295. · doi:10.1007/BF02932410
[6] B. Korte and W. Oberhofer, ”Zwei Algorithmen zur Lösung eines komplexen Reinhenfolgeproblems”,Unternehmensforschung 12 (1968) 217–362. · Zbl 0167.18403 · doi:10.1007/BF01918332
[7] B. Korte and W. Oberhofer, ”Zur Triangulation von Input-Output Matrizen”,Jahrbücher für Nationalökonomie und Statistik 182 (1969) 398–433.
[8] H.W. Lenstra, Jr., ”The acyclic subgraph problem”, Report BW26, Mathematisch Centrum (Amsterdam, 1973). · Zbl 0304.90112
[9] J.F. Mascotorchino and P. Michaud,Optimisation en analyse ordinale des données (Masson, Paris, 1979).
[10] H. Wessels, ”Triangulation und Blocktriangulation von Input-Output Tabellen”,Deutsches Institut für Wirtschaftsforschung: Beiträge aur Strukturforschung, Heft 63, Berlin, 1981.
[11] H.P. Young, ”On permutations and permutation polytopes”,Mathematical Programming Study 8 (1978) 128–140. · Zbl 0424.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.