pith. sign in

arxiv: 2107.08468 · v3 · submitted 2021-07-18 · 🧮 math.OC

On the facet pivot simplex method for linear programming

Yaguang Yang This is my paper

Pith reviewed 2026-05-24 13:28 UTC · model grok-4.3

classification 🧮 math.OC
keywords linear programmingsimplex methodfacet pivotvertex pivotNetlib test problemspolynomial algorithms
0
0 comments X

The pith

A facet pivot simplex method for linear programming performs better than the classic vertex pivot method in benchmark tests.

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

The paper introduces a facet pivot simplex method as an alternative to Dantzig's vertex pivot simplex method for solving linear programming problems. Through numerical tests on standard benchmark sets, the author shows the new method requires fewer iterations or less time in many cases. The central hope is that this different pivoting strategy could eventually yield a polynomial-time simplex algorithm, something that has not been found despite decades of work on the vertex version. If the facet approach scales well, it would change how large-scale linear programs are solved in practice by offering a new family of pivot rules.

Core claim

The facet pivot simplex method pivots on facets rather than vertices and numerical testing on Netlib problems indicates it is very promising compared to the vertex pivot method, raising the possibility of a polynomial pivot simplex algorithm for linear programming.

What carries the argument

The facet pivot simplex method, which selects pivot elements by moving between facets of the feasible region instead of between vertices.

If this is right

  • The facet pivot method may solve many linear programs with fewer pivots than the vertex pivot method.
  • Availability of a Matlab implementation allows direct comparison and further development of facet-based rules.
  • Success of facet pivoting would encourage search for other non-vertex pivot strategies that could be polynomial.
  • If a polynomial version is found, it would settle the long-open question of whether a polynomial simplex algorithm exists.

Where Pith is reading between the lines

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

  • The facet approach might extend to other polyhedral problems where vertex enumeration is expensive.
  • Comparing iteration counts alone may miss cases where facet pivots involve heavier arithmetic per step.
  • Hybrid methods that switch between facet and vertex rules on different problem classes could be tested.

Load-bearing premise

Numerical testing on Netlib problems is enough to show the facet pivot method is very promising and may lead to polynomial algorithms.

What would settle it

A collection of linear programs, including some from Netlib or larger instances, on which the facet pivot method requires more iterations or fails to solve faster than the vertex pivot method across repeated runs.

read the original abstract

Dantzig's vertex pivot simplex method has been published for more than seven decades. Amazingly, it remains one of the most efficient methods to solve linear programming (LP) problem after numerous efforts trying to find some better methods. In this paper, we propose a facet pivot simplex method and demonstrate by numerical testing that the new method is very promising compared to the vertex pivot method. Since there is no polynomial pivot simplex algorithm for linear programming problems after many decades of effort, we hope that this new type of pivot algorithm will give us some hope to find a polynomial pivot simplex method for linear programming problems. A Matlab implementation of the facet pivot algorithm and Netlib benchmark test problems are available in Matlab file exchange website.

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

3 major / 2 minor

Summary. The manuscript proposes a facet pivot simplex method for linear programming as an alternative to Dantzig's vertex pivot approach. It reports numerical experiments on Netlib test problems indicating that the facet pivot method is faster, and expresses the hope that this pivot strategy may eventually lead to a polynomial-time simplex algorithm. A Matlab implementation is made available via the Matlab File Exchange.

Significance. The public release of the implementation and benchmark data is a clear strength for reproducibility. If the reported speed-ups on Netlib instances prove robust under broader testing and the facet pivot rule can be shown to possess favorable theoretical properties, the work could open a new line of inquiry into non-vertex pivot rules. At present the significance remains modest because the central empirical claim rests on a single, well-known but limited test collection and lacks supporting complexity analysis.

major comments (3)
  1. [§4 and abstract] §4 (Numerical Experiments) and the abstract: the claim that the facet pivot method is 'very promising' is supported only by comparisons against the basic vertex pivot rule on the Netlib collection. No results are presented against established modern rules (steepest-edge, Devex, or dual steepest-edge), nor are any worst-case iteration bounds or complexity arguments given; this leaves the 'very promising' assessment and the polynomial-algorithm hope unsupported by the evidence provided.
  2. [§3] §3 (Algorithm Description): the facet pivot rule is defined via a sequence of linear systems whose size grows with the number of facets visited, yet no operation-count analysis or comparison of per-iteration cost versus the vertex pivot rule is supplied. Without this accounting it is impossible to determine whether the observed iteration reduction translates into a net computational advantage once the increased linear-algebra work is included.
  3. [Table 2] Table 2 (or equivalent results table): several Netlib instances are known to be degenerate or highly structured; the paper does not report degeneracy-handling mechanisms or anti-cycling safeguards for the facet pivot rule, raising the possibility that the reported speed-ups are partly an artifact of the test-set composition rather than a general property of the method.
minor comments (2)
  1. [abstract] The abstract states that 'a Matlab implementation ... are available' but does not give the exact file-exchange URL or repository commit; adding this information would improve reproducibility.
  2. [§2] Notation for the facet basis and the associated tableau is introduced without an explicit comparison table to the standard vertex-basis notation; a short side-by-side glossary would aid readers familiar with classical simplex terminology.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the constructive comments. We respond to each major point below, indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: [§4 and abstract] §4 (Numerical Experiments) and the abstract: the claim that the facet pivot method is 'very promising' is supported only by comparisons against the basic vertex pivot rule on the Netlib collection. No results are presented against established modern rules (steepest-edge, Devex, or dual steepest-edge), nor are any worst-case iteration bounds or complexity arguments given; this leaves the 'very promising' assessment and the polynomial-algorithm hope unsupported by the evidence provided.

    Authors: We agree the experiments compare only against the basic vertex pivot rule on Netlib instances. The manuscript introduces the facet pivot concept and provides initial empirical evidence of iteration reduction; modern pivot rules are variants of the vertex approach and were outside the initial scope. We will revise the abstract and §4 to moderate phrasing from 'very promising' to 'promising in initial tests' and add an explicit statement that comparisons to steepest-edge/Devex rules and any complexity analysis remain future work. The polynomial-time hope is presented as an open aspiration, not a claim supported by proof. revision: partial

  2. Referee: [§3] §3 (Algorithm Description): the facet pivot rule is defined via a sequence of linear systems whose size grows with the number of facets visited, yet no operation-count analysis or comparison of per-iteration cost versus the vertex pivot rule is supplied. Without this accounting it is impossible to determine whether the observed iteration reduction translates into a net computational advantage once the increased linear-algebra work is included.

    Authors: Section 3 emphasizes the algorithmic definition. We will insert an operation-count subsection comparing the cost of the growing linear systems against standard basis updates in the vertex rule, including flop estimates and conditions under which iteration savings may offset the extra work. revision: yes

  3. Referee: [Table 2] Table 2 (or equivalent results table): several Netlib instances are known to be degenerate or highly structured; the paper does not report degeneracy-handling mechanisms or anti-cycling safeguards for the facet pivot rule, raising the possibility that the reported speed-ups are partly an artifact of the test-set composition rather than a general property of the method.

    Authors: Degeneracy handling is not described in the text. The released Matlab code applies an adaptation of Bland's least-index rule to the facet selection step. We will add a paragraph in §3 and §4 detailing these safeguards and confirming they were active on the reported Netlib runs. revision: yes

standing simulated objections not resolved
  • A worst-case iteration bound or complexity analysis establishing polynomial-time behavior for the facet pivot rule.

Circularity Check

0 steps flagged

No circularity: empirical proposal with external numerical validation

full rationale

The paper proposes a facet pivot simplex algorithm and validates it via direct numerical experiments on the external Netlib benchmark set. No derivation, prediction, or first-principles claim is present that reduces by construction to fitted inputs, self-citations, or renamed ansatzes. The method is defined independently of its test outcomes, and performance claims are statistical comparisons against an external baseline rather than tautological re-statements of the algorithm itself. This is a standard non-circular empirical contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No information available from abstract regarding free parameters, axioms or invented entities.

pith-pipeline@v0.9.0 · 5635 in / 929 out tokens · 21142 ms · 2026-05-24T13:28:27.445307+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

32 extracted references · 32 canonical work pages

  1. [1]

    Avis and V

    D. Avis and V. Chv` atal, Notes on Bland’s pivoting rule, Mathematic al Program- ming Study, 8, 24-34, (1978)

    work page 1978

  2. [2]

    Beale, (1955), Cycling in the dual simplex method, Naval Res earch Logis- tics Quarterly, 2(4), 269–75

    E.M.L. Beale, (1955), Cycling in the dual simplex method, Naval Res earch Logis- tics Quarterly, 2(4), 269–75

    work page 1955

  3. [3]

    R. G. Bland, New finite pivoting rules for the simplex method, Mathe matics of Operations Research, 2(2), 103-107, (1977)

    work page 1977

  4. [4]

    Browne, J

    S. Browne, J. Dongarra, E. Grosse, T. Rowan, The Netlib mathematical software repository. DLib magazine. http://www.dlib.org/dlib/september95/netlib/09browne.html (1995)

    work page 1995

  5. [5]

    Dantzig, Programming in a linear structure, Econometrica 17 , 73-74, (1949)

    G.B. Dantzig, Programming in a linear structure, Econometrica 17 , 73-74, (1949)

    work page 1949

  6. [6]

    Dantzig, Linear programming and extensions, Princeton Univ ersity Press, Princeton, 1963

    G.B. Dantzig, Linear programming and extensions, Princeton Univ ersity Press, Princeton, 1963

    work page 1963

  7. [7]

    Friedmann, A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games., In: IPCO, pp

    O. Friedmann, A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games., In: IPCO, pp. 192-206, (2011)

    work page 2011

  8. [8]

    Goldfarb and W.Y

    D. Goldfarb and W.Y. Sit, Worst case behavior of the steepest ed ge simplex method, Discrete Applied Mathematics, 1, 277-285, (1979)

    work page 1979

  9. [9]

    H. J. Greenberg, Klee-Minty polytope shows exponential time co m- plexity of simplex method, University of Colorado at Denver, http://www.cudenver.edu/ hgreenbe, (1997)

    work page 1997

  10. [10]

    Hoffman, Cycling in the simplex algorithm, Washington DC: Natio nal Bureau of Standards, Report 2974, 1953

    A.J. Hoffman, Cycling in the simplex algorithm, Washington DC: Natio nal Bureau of Standards, Report 2974, 1953

    work page 1953

  11. [11]

    Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics, 4, 367-377, (1973)

    R.G. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics, 4, 367-377, (1973)

    work page 1973

  12. [12]

    Kalai and D

    G. Kalai and D. Kleitman, A quasi-polynomial bound for the diamet er of graphs of polyhedra, Bulletin of the American Mathematical Society, 26, 31 5-316, (1992)

    work page 1992

  13. [13]

    Kitahara and S

    T. Kitahara and S. Mizuno, Klee-Minty’s LP and upper bounds for Dantzig’s simplex method, Operations Research Letters, 39(2), 88-91, (2 011)

    work page

  14. [14]

    Karmarkar, A new polynomial-time algorithm for linear program ming, Combi- natorica, Vol

    N. Karmarkar, A new polynomial-time algorithm for linear program ming, Combi- natorica, Vol. 4, pp. 375-395, (1984)

    work page 1984

  15. [15]

    Klee and G.J

    V. Klee and G.J. Minty, How good is the simplex algorithm? In O. Shish a, editor, Inequalities, III, 159-175. Academic Press, New York, NY, (1972 ). 25

    work page 1972

  16. [16]

    Y. Liu, Y. Tu, Z. Zhang, The row pivoting method for linear progr amming, Omega, DOI: 2020.102354, (2021)

    work page arXiv 2020

  17. [17]

    D. G. Luenberger, Linear and nonlinear programming, Second e dition, Addision- Wesley Publishing Company, Inc., Menlo Park, 1984

    work page 1984

  18. [18]

    Lustig, R

    I. Lustig, R. Marsten, and D. Shannon, Computational exper ience with a primal- dual interior-point method for linear programming, Linear Algebra a nd Its Appli- cations, Vol. 152, pp. 191-222, (1991)

    work page 1991

  19. [19]

    Lustig, R

    I. Lustig, R. Marsten, D. Shannon, On implementing Mehrotra’s predictor- corrector interior-point method for linear programming, SIAM jou rnal on Opti- mization, Vol. 2, pp. 432-449 (1992)

    work page 1992

  20. [20]

    Mehrotra, On the implementation of a primal-dual interior poin t method, SIAM Journal on Optimization, 2, pp

    S. Mehrotra, On the implementation of a primal-dual interior poin t method, SIAM Journal on Optimization, 2, pp. 575-601, (1992)

    work page 1992

  21. [21]

    Ploskas and N

    N. Ploskas and N. Samaras, Pivoting rules for the revised simplex algorithm, Yu- goslav Journal of Operations Research, 24(3), 321-332, (2014 )

    work page 2014

  22. [22]

    Santos, A counterexample to the Hirsch conjecture, Anna ls of Mathematics, 176, 383-412, (2012)

    F. Santos, A counterexample to the Hirsch conjecture, Anna ls of Mathematics, 176, 383-412, (2012)

    work page 2012

  23. [23]

    Sukegawa, An asymptotically improved upper bound on the dia meter of poly- hedra, Discrete & Computational Geometry 62 (3), 690-699, (20 19)

    N. Sukegawa, An asymptotically improved upper bound on the dia meter of poly- hedra, Discrete & Computational Geometry 62 (3), 690-699, (20 19)

    work page

  24. [24]

    M. J. Todd, An improved Kalai–Kleitman bound for the diameter of a polyhedron, SIAM Journal on Discrete Mathematics, 26(2), 1944-1947, (201 4)

    work page 1944

  25. [25]

    Vitor and T

    F. Vitor and T. Easton, The double pivot simplex method, Mathem atical Methods of Operations Research, 87(1), 109-137, (2018)

    work page 2018

  26. [26]

    Yang, CurveLP-a MATLAB implementation of an infeasible inter ior-point al- gorithm for linear programming, Numerical Algorithms, Vol

    Y. Yang, CurveLP-a MATLAB implementation of an infeasible inter ior-point al- gorithm for linear programming, Numerical Algorithms, Vol. 74 (4), p p. 967-996 (2017)

    work page 2017

  27. [27]

    Yang, A facet enumeration algorithm for convex polytopes, arXiv:1909.11843 [math.OC], (2019)

    Y. Yang, A facet enumeration algorithm for convex polytopes, arXiv:1909.11843 [math.OC], (2019)

    work page arXiv 1909

  28. [28]

    Yang, Arc-search techniques for interior-point methods, CRC Press, Boca Ra- ton, 2020

    Y. Yang, Arc-search techniques for interior-point methods, CRC Press, Boca Ra- ton, 2020

    work page 2020

  29. [29]

    Yang, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, Research in the Mathematical Sciences, 7, 34, (2020)

    Y. Yang, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, Research in the Mathematical Sciences, 7, 34, (2020)

    work page 2020

  30. [30]

    Yang, Cycling problems in linear programming, arXiv:2101.01805 [math.OC], (2021)

    Y. Yang, Cycling problems in linear programming, arXiv:2101.01805 [math.OC], (2021). 26

    work page arXiv 2021

  31. [31]

    Yang, On the facet pivot simplex method for linear programmin g II: a linear iteration bound, arXiv:2201.00193 [math.OC], (2022)

    Y. Yang, On the facet pivot simplex method for linear programmin g II: a linear iteration bound, arXiv:2201.00193 [math.OC], (2022)

    work page arXiv 2022

  32. [32]

    Z¨ ornig, Systematic construction of examples for cycling in t he simplex method, Computers & Operations Research, 33(8), 2247-2262, (2006)

    P. Z¨ ornig, Systematic construction of examples for cycling in t he simplex method, Computers & Operations Research, 33(8), 2247-2262, (2006). 27

    work page 2006