Hard Linear Programs
This project investigates the computational complexity and algorithmic frontiers of "hard" linear programs—LP formulations that are provably difficult for simplex, interior-point, and first-order methods due to their geometric structure. By characterizing the conditions under which LPs become intractable, we aim to develop problem-specific pre-processing and decomposition techniques that bypass these bottlenecks.
🧑🎓 IOL Project Members
🤝 External Project Members
🪙 Funding
This project is being funded by the Berlin Mathematics Research Center MATH+ (project ID EF-LI-Opt-5), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from October 2026 to September 2029.
🔬 Project Description
Linear programming is one of the most mature and widely used tools in optimization, yet not all LPs are created equal. While most practical LPs are solved efficiently by simplex or interior-point methods, there exist classes of LPs—characterized by extreme geometric properties such as poor conditioning, near-degeneracy, or high facet complexity—where all standard methods struggle significantly.
This project pursues three directions: (1) Characterizing geometric properties (e.g., diameter of the feasible polyhedron, curvature of the central path, conditioning of basis inverses) that correlate with practical difficulty; (2) Developing pre-processing and reformulation techniques that transform hard LPs into more tractable forms without changing the optimal solution; (3) Decomposition strategies that split hard LPs into coupled, easier subproblems that can be solved via complementary methods (simplex for combinatorial structure, first-order for continuous structure).