Interior point methods solve some linear programs with fewer steps
Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
Data Structures and Algorithms
Summary
Linear programming is a way to find the best solution within certain limits, but some problems can take a long time to solve. The authors discuss a technique that uses a special measure called straight line complexity to limit how many steps an algorithm needs. They address tricky parts like how to start the method and how to keep calculations simple and accurate. Their work presents a way to initialize and round the process that works in guaranteed reasonable time for certain problem types.
What this means in practice
- •For optimization software developers: Implement interior point methods with guaranteed step bounds and controlled numerical complexity for special linear program classes.
- •For operations research teams: Optimize resource or logistics planning problems formulated as two-variable-per-inequality linear programs with strong guarantees on running time and accuracy.
A theory result. No direct application yet.
Authors
Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh
Abstract
Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.