Simplex pivot rule¶
Choose among eligible simplex pivot moves by a specified entering or leaving rule, from ordinary LP variables to network-flow arcs.
Core Idea¶
A simplex pivot rule chooses among currently eligible moves in a simplex method. It can refine the entering choice, the leaving choice, or both. The chosen move is then carried out by the surrounding solver. The selected Devex member uses dynamically weighted LP pivot choices in Harris's original abstract; Bland's least-index rule and network-simplex arc choices show that no single numerical score or tableau format defines the family.[ref-85ba1ccd0d90][ref-98cd66990de5][^ref-78911a257418]
Scope of Application¶
The rule requires a feasible simplex state, a method-defined eligible set and a legal pivot-update interface. Ordinary LP uses tableau variables and ratio conditions. The inspected capacitated network method uses a tree with non-tree arcs at bounds and chooses eligible arcs by reduced cost and bound status. The signs and updates depend on the stated solver variant.[ref-98cd66990de5][ref-78911a257418]
Harris's Devex paper and Tarjan's network study were inspected only through original publisher abstracts. They support their visible claims about choices and limited comparisons, not an exact Devex formula or a general polynomial simplex guarantee.[ref-85ba1ccd0d90][ref-8b07c7d4fb8d]
Clarity¶
Ask three questions: Which moves are eligible, which one does this rule select, and what update follows? The first and third belong to the solver; the middle is the pivot rule. A generic ranking of graph edges without a simplex feasible state and legal update does not qualify.[ref-98cd66990de5][ref-78911a257418]
Manages Complexity¶
When several moves are legal, a rule makes the next choice determinate or strategically directed. Bland's least-index refinement yields a finite ordinary-LP method under his theorem. The Devex abstract reports time and iteration comparisons on three LP cases. Neither result establishes that all pivot rules are finite or that one is always faster.[ref-98cd66990de5][ref-85ba1ccd0d90]
Abstract Reasoning¶
Hold the eligible set fixed and vary only the choice rule. The selected move can change without changing the optimization problem. Then trace the solver's actual update: Murty's network pivot may exchange a tree arc, or the entering arc can itself drop and flip between bounds while the tree stays unchanged. A basis exchange is therefore too narrow as a universal requirement.[ref-98cd66990de5][ref-78911a257418]
Knowledge Transfer¶
The selection interface transfers between ordinary LP tableaux and network-flow simplex: filter legal moves, refine the choice, then execute the variant's update. LP variables and network arcs fill those roles differently. Bland's no-cycling proof, Harris's reported Devex comparisons and Murty's bound-flip case remain tied to their stated settings.[ref-98cd66990de5][ref-85ba1ccd0d90][^ref-78911a257418]
Example¶
In an ordinary feasible LP tableau, Bland's Rule I selects the lowest-index eligible entering variable and lowest-index eligible leaving variable; he proves that this rule cannot cycle. In Murty's minimum-cost-flow network, reduced costs identify eligible non-tree entering arcs. The chosen arc defines a fundamental cycle and a legal update; his worked example exchanges arcs (1,10) and (9,11), while another permitted branch flips an arc's bound without replacing a tree arc. Both cases have eligible-move selection, but their carriers and updates differ.[ref-98cd66990de5][ref-78911a257418]
Neighborhood in Abstraction Space¶
Simplex pivot rule sits in a sparse region of the domain-specific corpus (97th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Network Simplex Algorithm — 0.77
- Fourier–Motzkin Elimination — 0.77
- Rational Choice Model — 0.76
- Randomized Rounding — 0.76
- Mixed Chinese Postman Problem — 0.76
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
Devex is one member, not the whole pivot-rule family. A complete simplex or network-simplex algorithm also handles feasibility, updates and stopping. A degenerate pivot need not improve the objective strictly. Tarjan's planar special-case polynomial result does not extend to all LP pivot rules.[ref-85ba1ccd0d90][ref-98cd66990de5][ref-78911a257418][ref-8b07c7d4fb8d]
References¶
[^ref-85ba1ccd0d90]: Paula M. J. Harris, “Pivot Selection Methods of the Devex LP Code,” Mathematical Programming 5 (1973): 1–28, doi:10.1007/BF01580108. Original publisher abstract, consulted 2026-10-09. Full article was not directly inspected; exact weight formulas are not claimed. [^ref-98cd66990de5]: Robert G. Bland, “New Finite Pivoting Rules for the Simplex Method,” Mathematics of Operations Research 2, no. 2 (1977): 103–107. Full original reproduction, especially printed pp. 103–104, including Rule I and Theorem 1.1; consulted 2026-10-09. [^ref-78911a257418]: Katta G. Murty, “Network Programming” (book, Prentice Hall, 1992), chapter 5 on algorithms for minimum-cost flow problems in pure networks. Full author-hosted chapter, especially §5.4 printed pp. 425–427 and Example 5.2 printed pp. 429–430; consulted 2026-10-09. The bound-flip branch is on printed p. 427. [^ref-8b07c7d4fb8d]: Robert E. Tarjan, “Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem,” Mathematics of Operations Research 16, no. 2 (1991): 272–291, doi:10.1287/moor.16.2.272. Original publisher abstract, consulted 2026-10-09. Full article was not directly inspected.