Towards Testable Theories of Linear Programming
The simplex method is a highly succesful algorithm in the context of Linear Programming and Mixed Integer Linear Programming, implemented in all state-of-the-art software packages. A number of theoretical models have previously been proposed to explain why the simplex method is efficient in practice, including average-case analysis, smoothed analysis, and parameterized analyses. Despite this concerted effort, existing approaches have a number of key limitations.
The project’s objective is to develop new mathematical approaches that address these limitations. The ideal outcome of this line of work is a mathematical framework for explaining the performance of the simplex method, and whose claims can be tested in computational experiments on real-world data. The project’s main output will be in theorems about the geometry and combinatorics of LP problems and convex polyhedra. Where applicable, computational experiments will be performed.
This project is funded by ANR JCJC grant ANR-24-CE48-2762 from October 2024 till September 2027.
People
The following people take part in TTTLP: