General information
Offer title : PhD student (M/F) (H/F)
Reference : UMR6158-BEABOU-017
Number of position : 1
Workplace : AUBIERE
Date of publication : 07 April 2025
Type of Contract : FTC PhD student / Offer for thesis
Contract Period : 36 months
Start date of the thesis : 1 June 2025
Proportion of work : Full Time
Remuneration : 2200 gross monthly
Section(s) CN : 01 - Interactions, particles, nuclei, from laboratory to cosmos
Description of the thesis topic
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.
Work Context
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.
Constraints and risks
The PhD candidate will be working in the MAAD axis at LIMOS under the supervision of Dr. Sophie HUIBERTS. Full proficiency in spoken and written English will be expected. This PhD position is funded by the ANR JCJC grant Towards Testable Theories of Linear Programming.