A note on small linear-ordering polytopes. (English) Zbl 0784.90063
Summary: We discuss the polyhedral structure of polytopes associated with the linear-ordering problem. We give explicit lists of facets of small linear-ordering polytopes for complete digraphs on up to seven nodes. For the latter we give a description that we believe to be complete.
MSC:
| 90C27 | Combinatorial optimization |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
Software:
LOLIBReferences:
| [1] | V. J. Bowman (1972), Permutation polyhedra,SIAM J. Appl. Math22, 580-589. · Zbl 0246.90030 · doi:10.1137/0122054 |
| [2] | J. S. de Cani (1969), Maximum likelihood paired comparison ranking by linear programming,Biometrika56, 537-545. · Zbl 0279.20038 · doi:10.1093/biomet/56.3.537 |
| [3] | T. Christof (1991), Ein Verfahren zur Transformation zwischen Polyederdarstellungen, Diplomarbeit, Universität Augsburg. |
| [4] | T. Christof, M. Jünger, and G. Reinelt (1991), A Complete Description of the Traveling Salesman Polytope on 8 Nodes,Oper. Res. Lett.10, 497-500. · Zbl 0744.90070 · doi:10.1016/0167-6377(91)90067-Y |
| [5] | T. Dridi (1980), Sur les distribution binaires associees a des distributions ordinales,Math. Sci. Humaines69, 15-31. · Zbl 0116.15002 |
| [6] | P. C. Fishburn (1990), Binary probabilities induced by rankings,SIAM J. Discrete Math.3, 478-488. · Zbl 0718.60006 · doi:10.1137/0403041 |
| [7] | P. C. Fishburn (1991), Induced Binary Probabilities and the Linear Ordering Polytope: A Status Report, AT & T Bell Laboratories. |
| [8] | M. Grötschel, M. Jünger, and G. Reinelt (1984), A cutting plane algorithm for the linear ordering problem,Oper. Res.32, 1195-1220. · Zbl 0188.50101 · doi:10.1287/opre.32.6.1195 |
| [9] | M. Grötschel, M. Jünger, and G. Reinelt (1985), Facets of the linear ordering polytope,Math. Programming33, 43-60. · Zbl 0204.57101 · doi:10.1007/BF01582010 |
| [10] | D. Hausmann (1980),Adjacency on Polytopes in Combinatorial Optimization, Hain, Meisenheim. · Zbl 0325.05019 |
| [11] | J. Leung and J. Lee (1990), Reinforcing Old Fences Gives New Facets, Report Yale University. |
| [12] | G. Reinelt (1985),The Linear Ordering Problem: Algorithms and Applications, Research and Exposition in Mathematics, Vol. 8, Heldermann-Verlag, Berlin. · Zbl 0554.90077 |
| [13] | R. Suck (1991), Geometric and Combinatorial Properties of the Polytope of Binary Choice Probabilities, Report, Universität Osnabrück. · Zbl 0751.90006 |
| [14] | S. N. Tschernikov (1971),Lineare Ungleichungen, Deutscher Verlag der Wissenschaften, Berlin. · Zbl 0221.15013 |
| [15] | H. P. Young (1978), On permutations and permutation polytopes,Math. Programming Stud.8, 128-140. · Zbl 0696.68068 · doi:10.1007/BFb0121198 |
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.
