Extreme behavior in linear programs and the simplex method

Abstract: Linear programs and the simplex method are at the core of mathematical optimization, both in theory and in practice. Today plenty of fascinating open questions remain about the behavior of the simplex method.

In this lecture we introduce natural geometric-topological structure one can associate to the set of all possible monotone paths of a linear program. Using this structure we are interested to find the extreme behavior of LPs regarding the following questions: a) How long can the monotone paths on a linear program be? b) How many different monotone paths can there be on a linear program?

We report on some highlights from three recent papers, the first joint work with Moise Blanchard (MIT) and Quentin Louveaux (U. Liege), the second with Sean Kafer (U. Waterloo) and Laura Sanità (TU Eindhoven) and the third with Christos Athanasiadis (U. Athens) and Zhenyang Zhang (U. California, Davis). Papers are available at and arxiv.org/abs/2002.00999, arxiv.org/abs/1909.12863 and arxiv.org/abs/2001.09575

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---