pith. sign in

arxiv: 2606.11820 · v1 · pith:OF3MEC5Mnew · submitted 2026-06-10 · 🧮 math.OC · cs.DS

On finding exact solutions of linear programs in the oracle model

Daniel Dadush , L\'aszl\'o A. V\'egh , Giacomo Zambelli This is my paper

Pith reviewed 2026-06-27 08:54 UTC · model grok-4.3

classification 🧮 math.OC cs.DS
keywords linear programmingoracle modelseparation oracleexact solutionscondition numberprimal-dual methodscutting-plane algorithms
0
0 comments X

The pith

An algorithm recovers exact primal and dual solutions to linear programs from a separation oracle in O(n² log(n/δ)) calls, independent of the objective.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to turn any approximate solver for linear programs into an exact solver when the feasible set is given only by a separation oracle. The number of oracle calls and arithmetic operations is bounded by quantities depending on dimension and a geometric condition number δ of the constraint system, with no dependence on the cost vector and no need to know δ in advance. The approach relies on geometric arguments to avoid bit-complexity techniques such as simultaneous Diophantine approximation. For rational input data the resulting procedure runs in polynomial time. It works in a black-box fashion and includes a general method to extract dual certificates from approximate solutions.

Core claim

We present an algorithm that finds exact primal and dual solutions using O(n² log(n/δ)) oracle calls and O(n⁴ log(n/δ)+n⁵ log log(1/δ)) arithmetic operations, where δ is a geometric condition number associated with the system (A,b). These bounds do not depend on the cost vector c and do not require a priori knowledge of δ. For rational data, log(1/δ) is polynomially bounded in the encoding size of (A,b), thus providing a polynomial-time algorithm. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions.

What carries the argument

A black-box reduction that extracts exact primal-dual solutions from approximate ones by combining a geometric condition number δ with a dual-certificate framework based on Burrell and Todd.

If this is right

  • The procedure yields a polynomial-time algorithm for rational data because log(1/δ) is bounded by a polynomial in the bit size of (A,b).
  • Running time is independent of the cost vector c, so the same bound applies uniformly for all objectives.
  • The method strengthens earlier oracle-model results by replacing bit-complexity arguments with purely geometric ones.
  • Any approximate solver whose error can be controlled relative to δ can be plugged in to obtain the stated exact-solution guarantees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If faster approximate oracles become available, the same reduction immediately improves exact-solution complexity.
  • The geometric condition number δ may serve as a natural parameter for analyzing other separation-oracle problems beyond linear programming.
  • The dual-certificate extraction technique could be reused in other settings where only primal approximations are returned by an oracle.

Load-bearing premise

That a black-box subroutine can be called repeatedly to produce approximate primal and dual solutions whose accuracy can be driven high enough relative to δ.

What would settle it

A concrete polyhedron given by a separation oracle together with a cost vector such that no sequence of O(n² log(n/δ)) oracle calls recovers exact optimal primal and dual solutions.

read the original abstract

We consider linear programming in the oracle model: $\max\{c^\top x \,:\, x\in P\}$, where the polyhedron $P=\{x\in\mathbb{R}^n\,:\, Ax\le b\}$ is given by a separation oracle. We present an algorithm that finds exact primal and dual solutions using $O(n^2\log(n/\delta))$ oracle calls and $O(n^4\log(n/\delta)+n^5\log\log(1/\delta))$ arithmetic operations, where $\delta$ is a geometric condition number associated with the system $(A,b)$. These bounds do not depend on the cost vector $c$ and do not require a priori knowledge of $\delta$. For rational data, $\log(1/\delta)$ is polynomially bounded in the encoding size of $(A,b)$, thus providing a polynomial-time algorithm. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions; the above running times are achieved when using the cutting plane method of Jiang, Lee, Song, and Wong (STOC 2020) for this subroutine. Whereas approximate solvers may return primal solutions only, we develop a general framework for extracting dual certificates based on the work of Burrell and Todd (Math. Oper. Res. 1985). Our algorithm strengthens results by Gr\"otschel, Lov\'asz, and Schrijver (Prog. Comb. Opt. 1984), and by Frank and Tardos (Combinatorica 1987) that rely on bit-complexity arguments. Our algorithm avoids rounding-based arguments such as simultaneous Diophantine approximation and uses geometric arguments instead.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript presents an algorithm for computing exact primal and dual solutions to a linear program max{c^T x : x in P} where P = {x : Ax ≤ b} is accessed via a separation oracle. The algorithm invokes a black-box approximate primal-dual solver and applies a Burrell-Todd-style dual-certificate extraction framework to produce exact solutions. It achieves O(n² log(n/δ)) oracle calls and O(n⁴ log(n/δ) + n⁵ log log(1/δ)) arithmetic operations, where δ is a geometric condition number of (A,b); the bounds are independent of c and require no a priori knowledge of δ. For rational data the running time is polynomial in the input size. The approach strengthens the results of Grötschel-Lovász-Schrijver and Frank-Tardos by replacing bit-complexity arguments with geometric ones and avoids simultaneous Diophantine approximation.

Significance. If the stated bounds and correctness hold, the result is significant because it supplies the first geometric (rather than bit-complexity) exact solver in the oracle model whose complexity is independent of the objective c and does not presuppose knowledge of δ. The black-box reduction to the Jiang-Lee-Song-Wong cutting-plane method is cleanly stated, and the dual-extraction framework is presented as a general tool. These features directly improve the earlier GLS and Frank-Tardos algorithms while preserving polynomial-time guarantees for rational instances.

minor comments (3)
  1. The abstract and §1 state that the running times are achieved when the Jiang et al. (STOC 2020) cutting-plane method is used as the approximate solver, but the precise error tolerances required by the dual-extraction routine (and how they translate into the log(1/δ) factors) are only sketched; a short explicit lemma relating the approximation accuracy parameter ε to δ would improve readability.
  2. Notation for the geometric condition number δ is introduced in the abstract and used throughout, yet its formal definition appears only after the main algorithm is described; moving the definition to §2 (Preliminaries) would make the complexity statements self-contained from the outset.
  3. The manuscript cites Burrell-Todd (1985) for the dual-certificate framework but does not include a self-contained pseudocode block for the extraction procedure; adding one (even as an appendix) would help readers verify that no hidden dependence on c or δ is introduced.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report contains no major comments.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation composes an external approximate solver (Jiang-Lee-Song-Wong cutting planes) with the Burrell-Todd dual-certificate framework and adds geometric arguments to obtain c-independent exact solutions and δ-free bounds; all load-bearing components are independent prior results with no self-citation, no fitted-parameter renaming, and no reduction of the claimed running times to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard modeling assumption that a separation oracle for the polyhedron is available and on the existence of a sufficiently accurate approximate primal-dual solver that can be invoked in black-box fashion.

axioms (2)
  • domain assumption A separation oracle for the polyhedron P is available and returns either a feasible point or a separating hyperplane.
    The entire oracle-model setting is defined by this assumption in the abstract.
  • domain assumption An approximate primal-dual solver (Jiang et al. STOC 2020) can be called as a black box and returns solutions of sufficient accuracy relative to δ.
    The stated running times are achieved precisely when this subroutine is used; the abstract treats it as an external primitive.

pith-pipeline@v0.9.1-grok · 5843 in / 1491 out tokens · 25130 ms · 2026-06-27T08:54:45.252616+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 1 canonical work pages

  1. [1]

    Allamigeon, D

    X. Allamigeon, D. Dadush, G. Loho, B. Natura, and L. A. V´ egh. Interior point methods are not worse than simplex.SIAM Journal on Computing, 54(5):FOCS22–178, 2025

    2025

  2. [2]

    D. S. Atkinson and P. M. Vaidya. A cutting plane algorithm for convex programming that uses analytic centers.Mathematical Programming, 69(1):1–43, 1995

    1995

  3. [3]

    Bertsimas and S

    D. Bertsimas and S. Vempala. Solving convex programs by random walks.Journal of the ACM (JACM), 51(4):540–556, 2004

    2004

  4. [4]

    U. Betke. Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem.Discrete & Computational Geometry, 32(3):317–338, 2004

    2004

  5. [5]

    L. Blum, F. Cucker, M. Shub, and S. Smale.Complexity and real computation. Springer Science & Business Media, 1998

    1998

  6. [6]

    L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines.Bulletin of the American Mathematical Society, 21(1):1–46, 1989

    1989

  7. [7]

    Brunsch and H

    T. Brunsch and H. R¨ oglin. Finding short paths on polytopes by the shadow vertex algorithm. In International Colloquium on Automata, Languages, and Programming, pages 279–290. Springer, 2013. 48

    2013

  8. [8]

    B. P. Burrell and M. J. Todd. The ellipsoid method generates dual variables.Mathematics of Operations Research, 10(4):688–700, 1985

    1985

  9. [9]

    M. B. Cohen, Y. T. Lee, and Z. Song. Solving linear programs in the current matrix multiplication time.Journal of the ACM (JACM), 68(1):1–39, 2021

    2021

  10. [10]

    Dadush and N

    D. Dadush and N. H¨ ahnle. On the shadow simplex method for curved polyhedra.Discrete & Computational Geometry, 56(4):882–909, 2016

    2016

  11. [11]

    Dadush, S

    D. Dadush, S. Huiberts, B. Natura, and L. A. V´ egh. A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix.Mathematical Pro- gramming, (204):135–206, 2024

    2024

  12. [12]

    Dadush, Z

    D. Dadush, Z. K. Koh, B. Natura, N. Olver, and L. A. V´ egh. A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1561–1572, 2024

    2024

  13. [13]

    Dadush, B

    D. Dadush, B. Natura, and L. A. V´ egh. Revisiting Tardos’s framework for linear programming: Faster exact solutions using approximate solvers. InProceedings of the 61st Annual IEEE Sym- posium on Foundations of Computer Science, 2020

    2020

  14. [14]

    Dadush, L

    D. Dadush, L. A. V´ egh, and G. Zambelli. Rescaling algorithms for linear conic feasibility.Math- ematics of Operations Research, 45(2):732–754, 2020

    2020

  15. [15]

    Dadush, L

    D. Dadush, L. A. V´ egh, and G. Zambelli. Geometric rescaling algorithms for submodular function minimization.Mathematics of Operations Research, 46(3):1081–1108, 2021

    2021

  16. [16]

    Dadush, L

    D. Dadush, L. A. V´ egh, and G. Zambelli. On finding exact solutions of linear programs in the oracle model. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2700–2722. SIAM, 2022

    2022

  17. [17]

    G. B. Dantzig. Anε-precise feasible solution to a linear program with a convexity constraint in 1/ε2 iterations independent of problem size. Technical report, Technical Report 92-5, Stanford University, 1992

    1992

  18. [18]

    Dunagan and S

    J. Dunagan and S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs.Mathematical Programming, 114(1):101–114, 2008

    2008

  19. [19]

    Eisenbrand and S

    F. Eisenbrand and S. Vempala. Geometric random edge.Mathematical Programming, 164(1- 2):325–339, 2017

    2017

  20. [20]

    Ekbatani, B

    F. Ekbatani, B. Natura, and A. L. V´ egh. Circuit imbalance measures and linear programming. In Surveys in Combinatorics 2022, London Mathematical Society Lecture Note Series, pages 64–114. Cambridge University Press, 2022

    2022

  21. [21]

    Frank and ´E

    A. Frank and ´E. Tardos. An application of simultaneous Diophantine approximation in combi- natorial optimization.Combinatorica, 7(1):49–65, 1987

    1987

  22. [22]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Geometric methods in combinatorial optimization. In Progress in combinatorial optimization, pages 167–183. Elsevier, 1984

    1984

  23. [23]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver.Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012

    2012

  24. [24]

    G¨ uler, A

    O. G¨ uler, A. J. Hoffman, and U. G. Rothblum. Approximations to solutions to systems of linear inequalities.SIAM Journal on Matrix Analysis and Applications, 16(2):688–696, 1995

    1995

  25. [25]

    Hoberg and T

    R. Hoberg and T. Rothvoß. An improved deterministic rescaling for linear programming al- gorithms. InInteger Programming and Combinatorial Optimization (IPCO), volume 10328 of Lecture Notes in Comput. Sci., pages 267–278. Springer, Cham, 2017. 49

    2017

  26. [26]

    H. Jiang. Minimizing convex functions with rational minimizers.Journal of the ACM, 70(1):1–27, 2022

    2022

  27. [27]

    Jiang, Y

    H. Jiang, Y. T. Lee, Z. Song, and S. C.-w. Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. InProceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 944–953, 2020

    2020

  28. [28]

    Jiang, Z

    S. Jiang, Z. Song, O. Weinstein, and H. Zhang. A faster algorithm for solving general lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 823–832, New York, NY, USA, 2021. Association for Computing Machinery

    2021

  29. [29]

    L. G. Khachiyan. A polynomial algorithm in linear programming (in Russian).Doklady Akademiia Nauk SSSR 224, 224:1093–1096, 1979. (English Translation: Soviet Mathematics Doklady 20, 191-194.)

    1979

  30. [30]

    Klatte and G

    D. Klatte and G. Thiere. Error bounds for solutions of linear equations and inequalities.Zeitschrift f¨ ur Operations Research, 41(2):191–214, 1995

    1995

  31. [31]

    Lamperski, R

    J. Lamperski, R. M. Freund, and M. J. Todd. An oblivious ellipsoid algorithm for solving a system of (in) feasible linear inequalities.Mathematics of Operations Research, 49(1):204–231, 2023

    2023

  32. [32]

    Y. T. Lee and A. Sidford. Solving linear programs with √ rank linear system solves.arXiv preprint arXiv:1910.08033, 2019

    work page arXiv 1910

  33. [33]

    Y. T. Lee, A. Sidford, and S. C.-w. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1049–1065. IEEE, 2015

    2015

  34. [34]

    A. K. Lenstra, H. W. Lenstra, and L. Lov´ asz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982

    1982

  35. [35]

    Nemirovski, S

    A. Nemirovski, S. Onn, and U. G. Rothblum. Accuracy certificates for computational problems with convex structure.Mathematics of Operations Research, 35(1):52–78, 2010

    2010

  36. [36]

    A. S. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization (in Russian). 1979. (English translation: Wiley-Intersci. Ser. Discrete Math. 15, John Wiley, New York, 1983.)

    1979

  37. [37]

    Pena and N

    J. Pena and N. Soheili. Projection and rescaling algorithm for finding most interior solutions to polyhedral conic systems.Mathematics of Operations Research, 47(4):3304–3316, 2022

    2022

  38. [38]

    Schrijver.Theory of linear and integer programming

    A. Schrijver.Theory of linear and integer programming. John Wiley & Sons, New York, 1998

    1998

  39. [39]

    M. Seysen. Simultaneous reduction of a lattice basis and its reciprocal basis.Combinatorica, 13(3):363–376, 1993

    1993

  40. [40]

    S. Smale. Mathematical problems for the next century.The Mathematical Intelligencer, 20(2):7– 15, 1998

    1998

  41. [41]

    Svensson, J

    O. Svensson, J. Tarnawski, and L. A. V´ egh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem.Journal of the ACM (JACM), 67(6):1–53, 2020

    2020

  42. [42]

    ´E. Tardos. A strongly polynomial algorithm to solve combinatorial linear programs.Operations Research, pages 250–256, 1986

    1986

  43. [43]

    J. F. Traub and H. Wo´ zniakowski. Complexity of linear programming.Operations Research Letters, 1(2):59–62, 1982. 50

    1982

  44. [44]

    Traub and J

    V. Traub and J. Vygen. An improved approximation algorithm for the asymmetric traveling salesman problem.SIAM Journal on Computing, 51(1):139–173, 2022

    2022

  45. [45]

    Tun¸ cel

    L. Tun¸ cel. Approximating the complexity measure of Vavasis–Ye algorithm is NP-hard.Mathe- matical Programming, 86(1):219–223, Sep 1999

    1999

  46. [46]

    P. M. Vaidya. A new algorithm for minimizing convex functions over convex sets.Mathematical Programming, 73(3):291–341, 1996

    1996

  47. [47]

    van den Brand

    J. van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–278, 2020

    2020

  48. [48]

    van den Brand, Y

    J. van den Brand, Y. T. Lee, A. Sidford, and Z. Song. Solving tall dense linear programs in nearly linear time. InProceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 775–788, 2020

    2020

  49. [49]

    S. A. Vavasis and Y. Ye. A primal-dual interior point method whose running time depends only on the constraint matrix.Mathematical Programming, 74(1):79–120, 1996. 51

    1996