Mixed Integer Linear Programming is a set of technologies underpinning much of modern logistics and manufacturing. The simplex method is one of the key algorithmic components of any MILP software package. This algorithm is known to be fast in practice, but the framework of worst-case analysis is unable to explain this observation. Different analysis frameworks have been proposed to explain the good performance of the algorithm, each with their own strengths and weaknesses. The PhD thesis will contribute to finding stronger and more rigorous upper bounds on the simplex method's running time.
The candidate will use a mathematical proof-based approach. Building on the state-of-the-art theoretical frameworks of smoothed analysis and deterministic input assumptions, the candidate will first improve on the strongest known theorems in this area. Second, the thesis will formulate a successor to these frameworks. This new framework will be based on novel understandings of the operating assumptions of modern MILP software.

Mixed Integer Linear Programming is a set of technologies underpinning much of modern logistics and manufacturing. The simplex method is one of the key algorithmic components of any MILP software package. This algorithm is known to be fast in practice, but the framework of worst-case analysis is unable to explain this observation. Different analysis frameworks have been proposed to explain the good performance of the algorithm, each with their own strengths and weaknesses. The PhD thesis will contribute to finding stronger and more rigorous upper bounds on the simplex method's running time.
The candidate will use a mathematical proof-based approach. Building on the state-of-the-art theoretical frameworks of smoothed analysis and deterministic input assumptions, the candidate will first improve on the strongest known theorems in this area. Second, the thesis will formulate a successor to these frameworks. This new framework will be based on novel understandings of the operating assumptions of modern MILP software.