Empirical Asymptotic Runtime Analysis of Linear Programming Algorithms

This paper takes an empirical look at asymptotic runtime growth rates for the most widely used algorithms for solving linear programming (LP) problems across a set of six optimization application areas that are known to produce large and difficult LP models. On the algorithm side, we consider the simplex method, interior-point methods, and PDHG. On the model side, we use a large language model (LLM) to create families of instances in different application areas, allowing us to study model types and sizes that are simultaneously synthetic and realistic. The results indicate that simple regression models typically predict observed runtimes quite well within a model class, and that asymptotic behavior can vary significantly between the different algorithms. This may have a significant impact on which algorithms will be most effective for solving large LP models in the future.

Source: arXiv:2604.16192v1 - http://arxiv.org/abs/2604.16192v1 PDF: https://arxiv.org/pdf/2604.16192v1 Original Link: http://arxiv.org/abs/2604.16192v1