A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
Abstract
In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity m1+o(1)log U log C. However, the m1+o(1) factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: m1.04 against m1.48 for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.
Related
- A Retrospective-Approximation Interior-Point Method
- Learned Preconditioning for a Primal-Dual Interior-Point Method
- Heat equation with singular drift which has bounded solution discontinuous at an interior point
- Clarabel: An interior-point solver for conic programs with quadratic objectives
- Observability Inequality for a Multi-Dimensional Degenerate Schrödinger Equation with an Interior Degeneracy Point
BibTeX
@misc{schatzle2026practical,
title = {{A Practical Combinatorial Interior Point Method for Minimum-Cost Flow}},
author = {Emil Schätzle and Simon Meierhans and Rasmus Kyng and Maximilian Probst Gutenberg},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18328},
eprint = {2610.18328},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18328},
}
RIS
TY - UNPB
TI - A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
AU - Emil Schätzle
AU - Simon Meierhans
AU - Rasmus Kyng
AU - Maximilian Probst Gutenberg
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18328
UR - https://arxiv.org/abs/2610.18328
AB - In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity m^1+o(1)log U log C. However, the m^1+o(1) factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: m^1.04 against m^1.48 for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.
ER -