Advanced Topics in Linear and Discrete Optimization (ADM III)

This course is the third and last in the sequence "Algorithmic Discrete Mathematics". It is meant for, but not restricted to, students in mathematics with an interest in a Master's Thesis (in discrete optimization and related areas) and PhD students of the BMS. The course takes place on Tuesdays and Thursdays, 10-12, in MA 550 at TU Berlin. It counts as a BMS Advanced Course.

The topic of the course is the complexity of linear programming. While results exist in abundance, the precise status is still unsettled. In fact, this is number 9 on Smale's list of mathematical problems for the 21st century.

The lecture on Tuesday, 27 Nov 2019 featured presentations by OSCAR developers.

Teaching assistant: Paco Criado

Contents

  1. Coding length and the ellipsoid method
  2. Simple polytopes and their graphs
  3. The Hirsch conjecture and its refutation by Santos
  4. Pivoting, Klee-Minty cubes etc
  5. Random linear programs and average case analysis
  6. Central paths, the interior point method and tropical linear programming

Notes

18 October 2018, 23 October 2018, 25 October 2018, 06 November 2018, 13 November 2018

Log-barrier interior point methods are not strongly polynomial

Presentation given 20 Oct 2017 at Bridging Continuous and Discrete Optimization, Simons Institute, Berkeley [pdf].

Exercises

Exercises 1: 8 November 2018, Exercises 2: 22 November 2018, Exercises 3: 13 December 2018, Exercises 4: 15 January 2019, Exercises 5: 31 January 2019

polymake snippets

References

  1. Allamigeon, Xavier; Benchimol, Pascal; Gaubert, Stéphane; Joswig, Michael: Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra Geom. 2 (2018), no. 1, 140–178.
  2. Blind, Roswitha; Mani-Levitska, Peter: Puzzles and polytope isomorphisms. Aequationes Math. 34 (1987), no. 2-3, 287–297.
  3. Borgwardt, Karl-Heinz: The simplex method. A probabilistic analysis. Algorithms and Combinatorics: Study and Research Texts, 1. Springer-Verlag, Berlin, 1987.
  4. Criado, Francisco; Santos, Francisco: Topological Prismatoids and Small Non-Hirsch Spheres, arXiv:1807.03030.
  5. Dadush, Daniel; Huiberts, Sophie: A friendly smoothed analysis of the simplex method. STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 390–403, ACM, New York, 2018.
  6. Even, Guy; Zadorojniy, Alexander: Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks. Ann. Oper. Res. 201 (2012), 159–167.
  7. Friedman, Eric J.: Finding a simple polytope from its graph in polynomial time. Discrete Comput. Geom. 41 (2009), no. 2, 249–256.
  8. Gärtner, Bernd; Henk, Martin; Ziegler, Günter M.: Randomized simplex algorithms on Klee-Minty cubes. Combinatorica 18 (1998), no. 3, 349–372.
  9. Grötschel, Martin; Lovász, László; Schrijver, Alexander: Geometric algorithms and combinatorial optimization. Second edition. Algorithms and Combinatorics, 2. Springer-Verlag, Berlin, 1993.
  10. Grünbaum, Branko: Convex polytopes. Second edition. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. Graduate Texts in Mathematics, 221. Springer-Verlag, New York, 2003.
  11. Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry.
  12. Joswig, Michael; Kaibel, Volker; Körner, Friederike: On the k-systems of a simple polytope. Israel J. Math. 129 (2002), 109–117.
  13. Joswig, Michael; Ziegler, Günter M.: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325–344.
  14. Kaibel, Volker; Schwartz, Alexander: On the complexity of polytope isomorphism problems. Graphs Combin. 19 (2003), no. 2, 215–230.
  15. Kalai, Gil: A simple way to tell a simple polytope from its graph. Journal of Combinatorial Theory, Series A 49 (1988), 381–383.
  16. Kalai, Gil: Linear programming, the simplex algorithm and simple polytopes. Lectures on mathematical programming (ismp97) (Lausanne, 1997). Math. Programming 79 (1997), no. 1-3, Ser. B, 217–233.
  17. Kim, Edward D.; Santos, Francisco: An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73–98.
  18. Matoušek, Jiří: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Universitext. Springer-Verlag, Berlin, 2003.
  19. Pach, János; Agarwal, Pankaj K.: Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995.
  20. Renegar, James: A mathematical view of interior-point methods in convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001
  21. Santos, Francisco: A counterexample to the Hirsch conjecture. Ann. of Math. (2) 176 (2012), no. 1, 383–412.
  22. Schrijver, Alexander: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986.
  23. Springborn, Boris A.: A unique representation of polyhedral types. Centering via Möbius transformations. Math. Z. 249 (2005), no. 3, 513–517.
  24. Wright, Stephen J.: Primal-dual interior-point methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
  25. Ziegler, Günter M.: Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995.
Home Teaching Presentations Projects Software

Last modified: Son Sep 15 09:09:41 UTC 2019 by mic