A strongly polynomial pivot rule for the simplex method
Let $A \in \mathbb{Q}^{m \times n}$ have full row rank, let $b \in \mathbb{Q}^m$ and $c \in \mathbb{Q}^n$, and consider the linear program $$\min\{c^{T} x : Ax = b,\ x \ge 0\},$$ given with an initial feasible basis and with finite optimal value. A simplex pivot rule passes from basis to basis by ordinary feasible simplex pivots along which the objective value does not increase; degenerate pivots are allowed. Klee and Minty showed that Dantzig's original rule can take exponentially many pivots, and superpolynomial lower bounds have since been proved for many other rules. Black constructed linear programs on which the shadow vertex rule takes exponentially many pivots whatever projection is chosen, and, for each norm, linear programs on which the steepest edge rule normalised by that norm does. Disser, Loho, Maat and Mosis proved superpolynomial lower bounds for whole classes of rules that choose among the improving pivots using only limited information about them: their ranks in a fixed global order (for rules with memory), or these ranks together with their reduced costs and objective improvements (for memoryless rules).
Problem. Is there a deterministic simplex pivot rule that reaches an optimal basis using a number of rational arithmetic operations and comparisons bounded by a polynomial in $m + n$ alone, with every intermediate rational number of bit length polynomial in the total input bit length? The choice of pivots and all auxiliary computations count toward the bound, so a pivot oracle of unbounded computational cost is not allowed.
Source: A long-standing question of linear programming, recalled by Black (2026) and by Disser, Loho, Maat and Mosis (2026); it bears on Smale's ninth problem (1998), a strongly polynomial algorithm for linear programming. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, linear programming, pivot rules, simplex method
References
@article{black2026,
author = {Black, Alexander E.},
title = {Exponential lower bounds for many pivot rules for the simplex method},
journal = {Math. Program.},
year = {2026},
doi = {10.1007/s10107-026-02325-5},
eprint = {2403.04886},
archivePrefix = {arXiv},
}
@inproceedings{disser2026,
author = {Disser, Yann and Loho, Georg and Maat, Matthew and Mosis, Nils},
title = {Lower bounds for ranking-based pivot rules},
booktitle = {43rd International Symposium on Theoretical Aspects of Computer Science ({STACS} 2026)},
series = {Leibniz Int. Proc. Inform. (LIPIcs)},
volume = {364},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2026},
pages = {31:1--31:19},
doi = {10.4230/LIPIcs.STACS.2026.31},
eprint = {2512.16684},
archivePrefix = {arXiv},
}
@article{smale1998,
author = {Smale, Steve},
title = {Mathematical problems for the next century},
journal = {Math. Intelligencer},
volume = {20},
number = {2},
year = {1998},
pages = {7--15},
doi = {10.1007/BF03025291},
}
@incollection{klee1972,
author = {Klee, Victor and Minty, George J.},
title = {How good is the simplex algorithm?},
booktitle = {Inequalities {III}},
editor = {Shisha, Oved},
publisher = {Academic Press},
address = {New York},
year = {1972},
pages = {159--175},
}
@misc{aim-strongly-polynomial-simplex,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A strongly polynomial pivot rule for the simplex method}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/093-strongly-polynomial-simplex.md},
note = {Entry 093 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00392, "A strongly polynomial pivot rule for the simplex method", clopen.solutions.