[en] Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. We begin by showing that combinatorial cubes have monotone diameter and Bland simplex height upper bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size monotone diameter. In contrast, we show that for many well-known combinatorial polytopes, the height is at least exponential. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths.
Disciplines :
Mathematics Computer science
Author, co-author :
Blanchard, Moise ✱; Massachusetts Institute of Technology - MIT
De Loera, Jesus ✱; University of California, Davis - UC Davis > Department of Mathematics
Louveaux, Quentin ✱; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète
✱ These authors have contributed equally to this work.
Language :
English
Title :
On the length of monotone paths in polyhedra
Publication date :
2021
Journal title :
SIAM Journal on Discrete Mathematics
ISSN :
0895-4801
eISSN :
1095-7146
Publisher :
Society for Industrial and Applied Mathematics, United States
I. Adler, C. Papadimitriou, and A. Rubinstein, On simplex pivoting rules and complexity theory, in Integer Programming and Combinatorial Optimization 2014, IPCO'14, Springer, Cham, Switzerland, 2014, pp. 13-24.
R. E. Behrend, Fractional perfect b-matching polytopes I: General theory, Linear Algebra Appl., 439 (2013), pp. 3822-3858.
D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Vol. 6, Athena Scientific, Belmont, MA, 1997.
N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier, On subdeterminants and the diameter of polyhedra, Discrete Comput. Geom., 52 (2014), pp. 102-115.
S. Borgwardt, J. A. De Loera, and E. Finhold, The diameters of network-flow polytopes satisfy the Hirsch conjecture, Math. Program., 171 (2018), pp. 283-309.
J. A. De Loera, New insights into the complexity and geometry of linear optimization, Optima, 87 (2011), pp. 1-11, http://www.mathopt.org/Optima-Issues/optima87.pdf.
J. A. De Loera, R. Hemmecke, and M. Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS-SIAM Ser. Optim., 14 SIAM, Philadelphia, 2013.
J. A. De Loera, S. Kafer, and L. Sanità, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, preprint, arXiv:1909.12863, 2019.
A. Del Pia and C. Michini, Short Simplex Paths in Lattice Polytopes, preprint, arXiv:1912.05712v2, 2020.
M. Develin, LP-orientations of cubes and crosspolytopes, Adv. Geom., 4 (2004), pp. 459-468.
J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Natl. Bur. Stand. (U.S.), 69B (1965), pp. 125-130.
J. Fearnley and R. Savani, The complexity of the simplex method, in Symposium on Theory of Computing 2015, STOC'15, ACM, New York, 2015, pp. 201-208.
M. J. Gallagher and W. D. Morris, A Proof of the Strict Monotone 5-Step Conjecture, preprint, arXiv:1806.03403, 2018.
D. Goldfarb and W. Y. Sit, Worst case behavior of the steepest edge simplex method, Discrete Appl. Math., 1 (1979), pp. 277-285, https://doi.org/10.1016/0166-218X(79)90004-0.
P. Gritzmann and B. Sturmfels, Minkowski addition of polytopes: Computation complexity and applications to Gröbner bases, SIAM J. Discrete Math., 6 (1993), pp. 246-269.
R. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Math., 4 (1973), pp. 367-377, https://doi.org/10.1016/0012-365X(73)90171-4.
G. Kalai, Upper bounds for the diameter and height of graphs of convex polyhedra, Discrete Comput. Geom., 8 (1992), pp. 363-372, https://doi.org/10.1007/BF02293053.
T. Kitahara, T. Matsui, and S. Mizuno, On the number of solutions generated by Dantzig's simplex method for LP with bounded variables, Pac. J. Optim., 8 (2012), pp. 447-455.
T. Kitahara and S. Mizuno, A bound for the number of different basic solutions generated by the simplex method, Math. Program., 137 (2013), pp. 579-586, https://doi.org/10.1007/s10107-011-0482-y.
V. Klee, A class of linear programming problems requiring a large number of iterations, Numer. Math., 7 (1965), pp. 313-321, https://doi.org/10.1007/BF01436525.
V. Klee, Heights of convex polytopes, J. Math. Anal. Appl., 11 (1965), pp. 176-190, https://doi.org/10.1016/0022-247X(65)90077-6.
V. Klee and G. J. Minty, How good is the simplex algorithm?, in Inequalities-III, Proceedings Third Symposium, 1969, Academic Press, New York, 1972, pp. 159-175.
T. Kuno, Y. Sano, and T. Tsuruda, Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm, Optim. Lett., 12 (2018), pp. 933-943, https://doi.org/10.1007/s11590-018-1276-4.
J. Mihalisin and V. Klee, Convex and linear orientations of polytopal graphs, Discrete Comput. Geom. 24 (2000), pp. 421-436, https://doi.org/10.1007/s004540010046.
D. J. Nadeff, The Hirsch conjecture is true for (0, 1)-polytopes, Math. Program., 45 (1989), pp. 109-110.
S. Onn and R. Pinchasi, A note on the minimum number of edge-directions of a convex polytope, J. Combin. Theory, Ser. A, 107 (2004), pp. 147-151, https://doi.org/10.1016/j. jcta.2004.03.008.
J. B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows, Math. Program., 77 (1997), pp. 109-129, https://doi.org/10.1007/BF02614365.
I. Pak, Four questions on Birkhoff polytope, Ann. Combin., 4 (2000), pp. 83-90.
J. Pfeifle and G. M. Ziegler, On the monotone upper bound problem, Exp. Math., 13 (2004), pp. 1-11, https://doi.org/10.1080/10586458.2004.10504519.
F. J. Rispoli, The monotonic diameter of the perfect matching and shortest path polytopes, Oper. Res. Lett., 12 (1992), pp. 23-27.
F. J. Rispoli, The monotonic diameter of the perfect 2-matching polytope, SIAM J. Optim., 4 (1994), pp. 455-460.
F. J. Rispoli, The monotonic diameter of traveling salesman polytopes, Oper. Res. Lett., 22 (1998), pp. 69-73.
F. J. Rispoli and S. Cosares, A bound of 4 for the diameter of the symmetric traveling salesman polytope, SIAM J. Discrete Math., 11 (1998), pp. 373-380.
F. Santos, Recent progress on the combinatorial diameter of polyhedra and simplicial complexes, in Symposium on Computational Geometry 2013, SoCG'13, 2013, pp. 165-166, https://doi.org/10.1145/2462356.2462408.
M. Tano, R. Miyashiro, and T. Kitahara, Steepest-edge rule and its number of simplex iterations for a nondegenerate lp, Oper. Res. Lett., 47 (2019), pp. 151-156, https://doi. org/10.1016/j.orl.2019.02.003.
T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments, Ann. Oper. Res., 46-47 (1993), pp. 203-233, https://doi.org/10.1007/BF02096264.
M. J. Todd, The monotonic bounded Hirsch conjecture is false for dimension at least 4, Math. Oper. Res., 5 (1980), pp. 599-601, https://doi.org/10.1287/moor.5.4.599.
M. J. Todd, The many facets of linear programming, Math. Program. Ser. B, 91 (2002), pp. 417-436, https://doi.org/10.1007/s101070100261.
D. M. Topkis, Adjacency on polymatroids, Math. Program., 30 (1984), pp. 229-237, https://doi.org/10.1007/BF02591887.
N. Zadeh, A bad network problem for the simplex method and other minimum cost flow algorithms, Math. Program., 5 (1973), pp. 255-266, https://doi.org/10.1007/BF01580132.
G. M. Ziegler, Lectures on Polytopes, Springer, New York, 1995.