Pith. sign in

REVIEW 2 major objections 3 minor 29 references

The paper presents linrax, a simplex-method linear program solver designed to run inside a just-in-time compiled, GPU-parallel, automatically differentiable numerical pipeline, and argues that it can solve general linear programs with linea

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 15:25 UTC pith:QWM45RWA

load-bearing objection A useful JAX simplex solver, but the dependent-constraint trick is wrong as written and can return suboptimal solutions on degenerate LPs. the 2 major comments →

arxiv 2509.19484 v2 pith:QWM45RWA submitted 2025-09-23 eess.SY cs.SY

linrax: A JAX Compatible, Simplex Method Linear Program Solver

Brendan Gould , Akash Harapanahalli , Samuel Coogan This is my paper
classification eess.SY cs.SY
keywords linear programmingsimplex methodtableau algorithmdependent constraintsautomatic differentiationjust-in-time compilationGPU parallelizationreachable set
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper introduces linrax, a simplex-method solver for linear programs that is built to be embedded as a subroutine in a numerical computing environment offering just-in-time compilation, GPU parallelization, and automatic differentiation. Its central claim is that it solves general LPs, including those with linearly dependent constraints, something the authors say is not possible with existing gradient-based solvers in that environment. The key modification is a marking step that keeps auxiliary-variable rows in the tableau after phase one but forces them to exit at the first opportunity, preserving the fixed array shapes required by traced compilation. If correct, this makes exact LP solutions available as differentiable, compilable components of larger control and robotics pipelines, as demonstrated on a reachability-based safety filtering example.

Core claim

The paper establishes that the two-phase tableau simplex method can be implemented under the strict tracing rules of a just-in-time compiling, automatically differentiating numerical library without sacrificing the ability to solve degenerate LPs. Standard simplex implementations discard rows of auxiliary variables left in the basis after phase one, but that changes array shapes and is disallowed when functions are traced. linrax instead takes the absolute value of those rows, marking the auxiliary variables so that they exit the basis at the first pivot of phase two with a ratio of zero. This keeps all array shapes static while still reaching the optimum, and the paper demonstrates the resu

What carries the argument

The central mechanism is the two-phase tableau simplex algorithm with a finite pivoting rule, plus a 'marking' step inserted before phase two. In Algorithm 2, line 19, the rows of the tableau corresponding to auxiliary variables that remain basic after phase one are replaced by their absolute values. The rationale is that feasible auxiliary variables are zero, so these rows will produce the smallest possible ratio in the ratio test whenever an entering variable threatens to affect them; the auxiliary variable exits on the first opportunity and will not re-enter because the objective does not depend on auxiliary variables. This avoids deleting rows, which would change the shape of the tableau

Load-bearing premise

That taking the absolute value of a tableau row for a basic auxiliary variable after phase one leaves the LP's optimum unchanged; the paper provides only an informal ratio-test argument, and if the transformed row alters the feasible set during later pivots, the solver can return an incorrect optimum.

What would settle it

Construct a small feasible LP with linearly dependent constraints where phase one leaves an auxiliary variable basic and its tableau row contains a nonzero entry in a non-auxiliary column, then solve with linrax and compare to a high-precision rational simplex; a mismatch in the objective value or optimal point would refute the central claim. An exhaustive search over small random degenerate LPs would settle it.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • LP subroutines can be JIT-compiled into larger pipelines, so repeated solves inside reachability or model-predictive-control loops can be fused and run on a GPU without losing gradient information.
  • Solutions are exact up to floating-point precision, replacing tolerance-limited approximations and improving solution quality on degenerate or dependent-constraint problems where gradient-based methods fail to converge.
  • Automatic differentiation through LP solutions enables gradient-based tuning of parameters that enter a pipeline only through LP solutions, as in the safety-filter example.
  • On small problems, performance is comparable to established non-differentiable solvers, and when embedded in a compiled pipeline the solver becomes an order of magnitude faster than general-purpose alternatives.

Where Pith is reading between the lines

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

  • Editorial: The absolute-value marking step rests on an unproved equivalence; the paper gives only an informal ratio-test argument. If a degenerate feasible LP leaves an auxiliary row with nonzero coefficients on original variables, the absolute value could change the feasible region and the returned optimum. This is testable by comparing linrax to a rational-arithmetic simplex on exhaustively gene
  • Editorial: The marking trick may generalize to other static-shape-constrained compilers or to other algorithms that need to avoid dynamic pruning, so the contribution may be broader than a single pipeline.
  • Editorial: Differentiating through a simplex path is nonsmooth because pivots are discrete; forward-mode automatic differentiation through the final tableau is valid only away from degeneracy, and gradients at degenerate vertices may be unstable or arbitrary. This could be probed by perturbing data around a degenerate optimal vertex.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper presents linrax, a JAX-compatible implementation of the two-phase tableau simplex method for linear programming. The authors argue that linrax is the first simplex-based LP solver in the JAX ecosystem and, crucially, that it can handle linearly dependent constraints—something they claim existing JAX-compatible first-order solvers cannot do. The main algorithmic novelty is a 'marking' step in Algorithm 2 (Line 19) that takes absolute values of tableau rows corresponding to basic artificial variables remaining after Phase 1, replacing the standard (and JAX-incompatible) practice of deleting such rows. The paper demonstrates linrax in a control-synthesis case study and benchmarks it against scipy, Gurobi, CVXPY, and JAXopt. The central claim is that linrax provides JIT compilation, GPU parallelization, and automatic differentiation through LP solutions while remaining numerically exact and robust to degeneracy.

Significance. If the algorithm were correct, linrax would fill a genuine gap: no existing JAX-compatible LP solver offers a simplex-based, exact method that composes with JAX transformations and handles degenerate, linearly dependent constraints. The benchmarks in Tables I and II, along with the open-source implementation, would make this a useful contribution to the control and optimization communities. However, the load-bearing 'marking' step is not a valid simplex operation and can change the feasible region of the LP, yielding suboptimal or incorrect solutions. The paper provides no proof of correctness for this step, and a concrete counterexample shows it fails. Thus the paper's main contribution is not supported.

major comments (2)
  1. [Algorithm 2, Line 19 (Section III-C)] The 'marking' step—replacing each tableau row of a remaining basic artificial variable with its absolute value—is not a valid algebraic transformation. A Phase 1 row of the form a_i + Σ α_j x_j = 0 (with RHS 0) represents the valid equality Σ α_j x_j = 0 on the original feasible set once a_i = 0. Taking absolute values replaces this with Σ |α_j| x_j = 0. When the α_j have mixed signs, this cuts the feasible region. For example, consider the LP: min -x1 subject to x1 - x2 = 0, -x1 + x2 = 0, x1,x2 ≥ 0. Phase 1 with Bland's rule terminates immediately with a1 and a2 basic at 0; the rows are a1 + x1 - x2 = 0 and a2 - x1 + x2 = 0. Line 19 turns these into x1 + x2 = 0 and x1 + x2 = 0, forcing x1 = x2 = 0. The algorithm then returns objective 0, whereas the true optimum is -∞ (the feasible set is x1 = x2 ≥ 0, and the objective is unbounded below). This directly contradicts the paper's claim to
  2. [Section III-C] The paper's justification for Line 19—that since every auxiliary variable has value 0 at the end of Phase 1, the marked rows receive a ratio of 0 in the ratio test—does not establish correctness. Even if the marked rows leave the basis on the first opportunity in Phase 2, the Phase 2 tableau is initialized with the modified constraints. The damage is done before any Phase 2 pivot. The row's equation is not a redundant constraint that can be harmlessly replaced; it is a genuine equality that, after marking, may exclude feasible points and change the optimum. A correctness proof for this modification is absent, and the counterexample above shows that no such proof can exist without additional conditions high are not stated or enforced.
minor comments (3)
  1. [Section I-A] Typo: 'tracibility' should be 'traceability'.
  2. [Algorithm 2, Line 17] The infeasibility check 'c_aux · x_aux > 0' is ambiguous because x_aux is not explicitly defined as the vector of artificial variable values. Clarify the notation.
  3. [Table II] CVXPY is reported as 'Fail' but the reason (crash vs. timeout) is not discussed. A brief explanation would help the reader interpret the benchmark.

Circularity Check

0 steps flagged

No circularity: linrax's solver claims are supported by external benchmarks and an independent algorithm implementation; self-citations appear only as background components.

full rationale

The paper's central claim is that linrax is the first JAX-compatible simplex LP solver that handles dependent constraints. This is an implementation and algorithmic claim, not a derived prediction fitted to the paper's own outputs. The benchmarks compare linrax against external solvers (scipy, gurobi, CVXPY, JAXopt) on independent test problems, providing non-circular evidence for the performance and convergence claims. The self-citations to the authors' prior tools (immrax, the lifting approach) are used as components in the case study and for background methodology, but the correctness of the solver or the claim of handling dependent constraints does not reduce to those citations. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from prior author work, and no ansatz is smuggled in via citation. The potential weakness in Algorithm 2, Line 19 (the absolute-value marking of auxiliary-variable rows) is a possible mathematical correctness gap, not a circularity: it concerns whether the algorithm returns the correct optimum, not whether the result is equivalent to its input by construction. Therefore no circular step is present.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The solver introduces no free parameters or new entities. The key unproven assumption is the correctness of the marking modification, which the paper argues informally.

axioms (4)
  • ad hoc to paper The 'marking' step (absolute value of rows for basic auxiliary variables) preserves the optimal solution of the LP.
    Algorithm 2, Line 19; the paper provides only an informal ratio-test argument and no formal proof.
  • standard math Standard two-phase simplex tableau updates with Bland's rule are correct and terminate.
    Section III-B; classical result.
  • domain assumption JAX transformation semantics (jit, grad, vmap) correctly handle the solver's internal operations.
    Section III-C; relies on JAX's static-shape tracing rules.
  • domain assumption The reachable-set refinements in Algorithm 1 produce a valid overapproximation.
    Section II-A; based on cited prior work [20, 21, 6].

pith-pipeline@v1.3.0-alltime-deepseek · 11954 in / 48221 out tokens · 301967 ms · 2026-08-04T15:25:06.537597+00:00 · methodology

0 comments
read the original abstract

We present linrax, the first simplex based linear program (LP) solver compatible with the JAX ecosystem. In many control algorithms, LPs are often automatically generated and frequently solved either offline or online in the control loop. This motivates the design of linrax, which is especially suited for compilation into a complex JAX-based pipeline as a subroutine. We discuss the challenges associated with implementing a general purpose LP solver under strict design requirements from JAX. Notably, we can solve general problems which may include dependent constraints-something not possible with existing JAX-compatible LP solvers that use first-order techniques and may fail to converge. We demonstrate the utility of linrax through several examples, including a robust control synthesis pipeline for a nonlinear vehicle model using automatic differentiation through a LP-based reachable set framework.

Figures

Figures reproduced from arXiv: 2509.19484 by Akash Harapanahalli, Brendan Gould, Samuel Coogan.

Figure 1
Figure 1. Figure 1: Nominal feedforward trajectory computed by MPC in Example [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The projection of the reachable sets obtained using the lifted embed [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Bounds on the reachable set of trajectories of the Van der Pol [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

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

29 extracted references · 1 canonical work pages

  1. [1]

    CasADi: a software framework for nonlinear optimization and opti- mal control,

    J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “CasADi: a software framework for nonlinear optimization and opti- mal control,”Mathematical Programming Computation, vol. 11, pp. 1– 36, Mar. 2019

    2019

  2. [2]

    Control-Lyapunov functions,

    E. D. Sontag, “Control-Lyapunov functions,” inOpen Problems in Mathematical Systems and Control Theory(V . Blondel, E. D. Sontag, M. Vidyasagar, and J. C. Willems, eds.), pp. 211–216, London: Springer, 1999

    1999

  3. [3]

    Control Barrier Functions: Theory and Applications,

    A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control Barrier Functions: Theory and Applications,” in 2019 18th European Control Conference (ECC), pp. 3420–3431, June 2019

    2019

  4. [4]

    Dantzig,Linear Programming and Extensions

    G. Dantzig,Linear Programming and Extensions. Princeton Land- marks in Mathematics and Physics, Princeton, NJ: Princeton Univer- sity Press, 2016

    2016

  5. [5]

    Robust Path Planning and Control For Polygonal Environments via Linear Programming,

    M. Bahreinian, E. Aasi, and R. Tron, “Robust Path Planning and Control For Polygonal Environments via Linear Programming,” in 2021 American Control Conference (ACC), pp. 5035–5042, May 2021. ISSN: 2378-5861

    2021

  6. [6]

    Efficient polyhedral enclosures for the reachable set of nonlinear control systems,

    S. M. Harwood and P. I. Barton, “Efficient polyhedral enclosures for the reachable set of nonlinear control systems,”Springer London, Feb

  7. [7]

    SciPy 1.0: Fundamental algorithms for scientific computing in python,

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, I. Polat, Y . Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen,...

    2020

  8. [8]

    Gurobi optimizer reference manual,

    Gurobi Optimization, LLC, “Gurobi optimizer reference manual,” 2024

    2024

  9. [9]

    CVXPY: A Python-embedded modeling language for convex optimization,

    S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,”Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016

    2016

  10. [10]

    Linear optimization on modern GPUs,

    D. G. Spampinato and A. C. Elster, “Linear optimization on modern GPUs,” in2009 IEEE international symposium on parallel & dis- tributed processing, pp. 1–8, IEEE, 2009

    2009

  11. [11]

    JAX: composable transformations of Python+NumPy programs,

    J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman- Milne, and Q. Zhang, “JAX: composable transformations of Python+NumPy programs,” 2018

    2018

  12. [12]

    immrax: A Paral- lelizable and Differentiable Toolbox for Interval Analysis and Mixed Monotone Reachability in JAX,

    A. Harapanahalli, S. Jafarpour, and S. Coogan, “immrax: A Paral- lelizable and Differentiable Toolbox for Interval Analysis and Mixed Monotone Reachability in JAX,” Apr. 2024. arXiv:2401.11608 [cs, eess, math]

    Pith/arXiv arXiv 2024

  13. [13]

    Kheperax: a Lightweight JAX-based Robot Control Environment for Benchmarking Quality-Diversity Al- gorithms,

    L. Grillotti and A. Cully, “Kheperax: a Lightweight JAX-based Robot Control Environment for Benchmarking Quality-Diversity Al- gorithms,” inProceedings of the Companion Conference on Genetic and Evolutionary Computation, GECCO ’23 Companion, (New York, NY , USA), pp. 2163–2165, Association for Computing Machinery, July 2023

    2023

  14. [14]

    JaxMARL: Multi-Agent RL Environments and Algorithms in JAX,

    A. Rutherford, B. Ellis, M. Gallici, J. Cook, A. Lupu, G. Ingvarsson, T. Willi, R. Hammond, A. Khan, C. S. de Witt, A. Souly, S. Bandy- opadhyay, M. Samvelyan, M. Jiang, R. Lange, S. Whiteson, B. Lac- erda, N. Hawes, T. Rockt ¨aschel, C. Lu, and J. Foerster, “JaxMARL: Multi-Agent RL Environments and Algorithms in JAX,”Advances in Neural Information Proces...

    2024

  15. [15]

    The DeepMind JAX Ecosystem,

    DeepMind, I. Babuschkin, K. Baumli, A. Bell, S. Bhupatiraju, J. Bruce, P. Buchlovsky, D. Budden, T. Cai, A. Clark, I. Danihelka, A. Dedieu, C. Fantacci, J. Godwin, C. Jones, R. Hemsley, T. Hen- nigan, M. Hessel, S. Hou, S. Kapturowski, T. Keck, I. Kemaev, M. King, M. Kunesch, L. Martens, H. Merzic, V . Mikulik, T. Norman, G. Papamakarios, J. Quan, R. Ring...

    2020

  16. [16]

    Optimistix: modular optimisation in JAX and equinox,

    J. Rader, T. Lyons, and P. Kidger, “Optimistix: modular optimisation in JAX and equinox,”arXiv:2402.09983, 2024

    Pith/arXiv arXiv 2024

  17. [17]

    Equinox: neural networks in JAX via callable PyTrees and filtered transformations,

    P. Kidger and C. Garcia, “Equinox: neural networks in JAX via callable PyTrees and filtered transformations,”Differentiable Program- ming workshop at Neural Information Processing Systems 2021, 2021

    2021

  18. [18]

    Efficient and modular implicit differentiation,

    M. Blondel, Q. Berthet, M. Cuturi, R. Frostig, S. Hoyer, F. Llinares- L´opez, F. Pedregosa, and J.-P. Vert, “Efficient and modular implicit differentiation,”arXiv preprint arXiv:2105.15183, 2021

    Pith/arXiv arXiv 2021

  19. [19]

    MPAX: Mathematical programming in JAX,

    H. Lu, Z. Peng, and J. Yang, “MPAX: Mathematical programming in JAX,”arXiv preprint arXiv:2412.09734, 2024

    arXiv 2024

  20. [20]

    Jaulin, M

    L. Jaulin, M. Kieffer, O. Didrit, and E. Walter,Applied interval analysis. Springer, 1st edition. ed., 2001

    2001

  21. [21]

    Rapid and Accurate Reachability Analysis for Nonlinear Dynamic Systems by Exploiting Model Redundancy,

    K. Shen and J. Scott, “Rapid and Accurate Reachability Analysis for Nonlinear Dynamic Systems by Exploiting Model Redundancy,” Computers & Chemical Engineering, vol. 106, Aug. 2017

    2017

  22. [22]

    Certified Robust Invariant Polytope Training in Neural Controlled ODEs,

    A. Harapanahalli and S. Coogan, “Certified Robust Invariant Polytope Training in Neural Controlled ODEs,” Aug. 2024. arXiv:2408.01273 [cs, eess, math]

    Pith/arXiv arXiv 2024

  23. [23]

    Presolving in linear program- ming,

    E. D. Andersen and K. D. Andersen, “Presolving in linear program- ming,”Mathematical Programming, vol. 71, pp. 221–245, Dec. 1995

    1995

  24. [24]

    Finding all linearly dependent rows in large-scale linear programming,

    E. D. Andersen, “Finding all linearly dependent rows in large-scale linear programming,”Optimization Methods and Software, vol. 6, pp. 219–227, Jan. 1995. Publisher: Taylor & Francis eprint: https://doi.org/10.1080/10556789508805634

    work page doi:10.1080/10556789508805634 1995

  25. [25]

    Parallelizing the dual revised simplex method,

    Q. Huangfu and J. A. J. Hall, “Parallelizing the dual revised simplex method,”Mathematical Programming Computation, vol. 10, pp. 119– 142, Mar. 2018

    2018

  26. [26]

    A general analysis of the convergence of ADMM,

    R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. Jordan, “A general analysis of the convergence of ADMM,” inProceedings of the 32nd international conference on machine learning(F. Bach and D. Blei, eds.), vol. 37 ofProceedings of machine learning research, (Lille, France), pp. 343–352, PMLR, July 2015

    2015

  27. [27]

    Notes on Bland’s pivoting rule,

    D. Avis and V . Chv´atal, “Notes on Bland’s pivoting rule,” inPolyhedral Combinatorics: Dedicated to the memory of D.R. Fulkerson(M. L. Balinski and A. J. Hoffman, eds.), pp. 24–34, Berlin, Heidelberg: Springer, 1978

    1978

  28. [28]

    Differentiable convex optimization layers,

    A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter, “Differentiable convex optimization layers,” inAdvances in neural information processing systems, pp. 9558–9570, 2019

    2019

  29. [2016]

    Accepted: 2016-07-20T19:25:14Z Publisher: Springer London

    2016