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 refines a simplex method's choice among currently eligible moves from a feasible basis or partition. It may choose an entering variable or arc, a leaving one, or both. Its criterion can be an index, an ordered scan or a computed weight. The rule selects a legal next step; the surrounding simplex algorithm supplies feasibility tests, state updates and stopping conditions.[1][2]
The selected queue member is Harris's Devex rule for LP pivot-column and row selection. Its original publisher abstract reports dynamically weighted choices and three LP comparisons, but does not expose the exact update formula here. Bland's least-index rule is a different ordinary-LP choice refinement. A network-simplex rule acts on eligible arcs of a flow network; its legal pivot update can exchange a tree arc or flip a nonbasic arc between bounds without changing the tree. Those unlike settings share the selection role, not one implementation.[3][1][2]
Structural Signature¶
- Current feasible simplex state. Ordinary LP uses a feasible tableau and basic variables; the inspected capacitated network method uses a spanning-tree partition plus non-tree arcs fixed at bounds. A bare ranking of objects without such a state is not this rule.[1][2]
- Eligible alternatives. The underlying variant identifies entering choices through its own reduced-cost and bound conditions and, where applicable, leaving choices through ratio or residual-capacity conditions. Signs depend on the stated formulation; if no eligible entering choice remains, the method may stop rather than invoke an active choice.[1][2]
- Choice refinement. The rule narrows permitted alternatives by a declared criterion. Bland selects least-index eligible variables; the Devex abstract describes weighted column and row choices. No universal numerical score is required.[1][3]
- Permitted update interface. The chosen move passes to a legal pivot update. In ordinary LP this normally exchanges basic variables; Murty explicitly allows a network entering arc also to be the dropping arc, switching its bound set while the tree stays the same. The update itself is a larger operation than the selection rule.[1][2]
The rule can still be defined when a particular iteration offers only one candidate; comparing multiple options every time is not a constitutive requirement.[1][2]
What It Is Not¶
It is not the complete simplex solver. Initial feasibility, reduced-cost evaluation, flow or tableau update and final optimality or unboundedness checks are performed by the surrounding method. It is also not a generic graph-edge priority rule: the edge must be eligible under a simplex basis/partition and its legal update. The network variant is a specialization, not a proof that all LP implementations use arcs or trees.[1][2]
Nor does every pivot strictly improve the objective. Degenerate simplex pivots can leave the current point or objective unchanged, and Murty distinguishes degenerate network steps. Bland's theorem proves finiteness for his stated Rule I, not for every choice rule; Tarjan's publisher abstract gives a polynomial result only for a restricted planar network case, not all LPs.[1][2][4]
Scope of Application¶
Use this identity inside a simplex method when there is a current feasible basis or partition, a method-defined eligible move set and a declared refinement of the entering or leaving selection. The inspected ordinary-LP source uses tableau variables under its primal maximization convention. The network source uses capacitated minimum-cost flow with tree and bound-fixed non-tree arcs. Their eligibility signs and update mechanics must not be silently interchanged.[1][2]
The Harris and Tarjan originals were inspected at publisher-abstract level only. Harris supports Devex's named choices and reported comparisons, not a reconstructed weight formula. Tarjan supports an independently studied network selection rule and scoped complexity claims, not a general polynomial simplex rule.[3][4]
Clarity¶
Separate three questions: Which moves are eligible under this solver? Which eligible move does the rule choose? What update does the solver then perform? A least-index choice and a weighted choice answer the middle question differently while both depend on a legal first and third step. This prevents an arbitrary score over variables or arcs from being mislabeled a pivot rule.[1][2][3]
Also ask which performance claim is being made. A proof that one rule cannot cycle is not a runtime comparison; a reported time and iteration comparison on three LP examples is not a universal ordering of rules.[1][3]
Manages Complexity¶
Eligibility may leave several valid next moves. A pivot rule makes the selection reproducible or strategically directed without redefining the optimization problem. In ordinary LP, Bland's deterministic index tie-breaking yields a finite method under his assumptions; Devex offers a different reported computational selection scheme. In a network model, a rule reduces many candidate entering arcs to a chosen arc while the fundamental-cycle machinery handles the legal update.[1][3][2]
Selection work and pivot count are separate quantities. Measuring one alone does not determine total running time, and the inspected abstracts do not establish a universal trade-off between them.[3][4]
Abstract Reasoning¶
Hold the feasible state and its eligible set fixed, then change only the refinement. The selected entrant or leaver may change; the feasible region and optimization objective do not. To explain a difference in iterations, degeneracy or runtime, identify the particular rule, instance and solver variant rather than attribute it to simplex in general.[1][3][2]
For a network candidate, test both legal update branches. If the entering arc is also the dropping arc, the bound changes and the tree remains; demanding a tree exchange would falsely reject that pivot. If no entering arc qualifies under Murty's stated optimality conditions, there is no active choice to refine.[2]
Knowledge Transfer¶
The selection interface transfers from LP tableaux to network-flow simplex: identify a feasible state, filter legal moves, refine the choice, then allow the variant's update. The carrier and eligibility semantics do not transfer unchanged. Bland's no-cycling proof and Murty's network bound-flip branch belong to their stated variants, while Harris's measured Devex comparisons cannot be projected onto network arcs without new evidence.[1][2][3]
A ranking rule outside simplex can resemble this pattern, but it lacks the simplex feasible-state and pivot-update commitments needed for this domain-specific name.
Examples¶
Ordinary LP: Devex member and a least-index contrast¶
For an ordinary feasible LP tableau, eligible entering variables satisfy the tableau's reduced-cost condition and eligible leaving variables satisfy its ratio condition. Harris's original Devex abstract describes dynamic weights for pivot-column selection and row-choice methods and reports time and iteration comparisons for three large LP cases. The exact weight recurrence is outside the inspected abstract. Bland gives a fully inspectable contrast: select the lowest-index eligible entrant and then the lowest-index eligible leaver; his Rule I cannot cycle. Both refine an eligible tableau choice, but only Bland's stated theorem supplies the no-cycling conclusion.[3][1]
Minimum-cost-flow network simplex¶
For Murty's capacitated network model, the feasible state is a tree basis with non-tree arcs at lower or upper bounds and associated node prices. Reduced costs and bound status identify eligible entering arcs. An entering arc defines a fundamental cycle, and residual capacities identify the dropping arc. Murty's worked example exchanges entering arc (1,10) with dropping arc (9,11). In another permitted branch, the entering arc is itself the dropping arc and switches bound set without changing the tree. The rule chooses among legal candidates; these flow and tree updates belong to the network-simplex method.[2]
Structural Tensions¶
The inspected sources do not establish a general unavoidable tension between selection effort and pivot count. Both should be reported when evaluating a rule, but the direction and size of any trade-off depend on a stated implementation and instance. Harris reports both for three LP comparisons; Tarjan discusses network pivot and runtime bounds under restricted assumptions. No broader monotonic claim is licensed here.[3][4]
Structural–Framed Character¶
The choice interface is structural within optimization: a current feasible state yields eligible moves, and a declared refinement picks one.[1][2] Its evaluative weight lies in computation time or termination behavior, but those outcomes are rule- and problem-dependent. Human designers choose and implement the refinement, while the rule's mathematical eligibility and update relation does not depend on a particular person or organization. Research journals and solver projects stabilize examples and names, but no institution constitutes the rule's identity. The vocabulary travels literally between LP tableaux and network-flow simplex when the feasible-state and pivot-update roles are filled; applied to generic non-simplex selection it becomes analogy. Recognition of this named method component requires simplex eligibility and a legal pivot-update interface. Its character: a domain-specific algorithmic choice rule with a portable selection skeleton and specialist operating conditions.
Structural Core vs. Domain Accent¶
The thin core is a selection among allowed continuations. The domain-bound substance is how LP or network simplex defines a feasible state, eligible pivot move and legal update. A network bound flip shows why “basis exchange” is too narrow as a universal core.[1][2] A generic selection algorithm without the simplex commitments is only an analogy to this named rule. Whether eligible-choice refinement across genuinely different domains warrants a separate Prime is a future-Prime question requiring independent cross-domain evidence; the simplex-specific rule does not clear that bar through vocabulary transfer alone.
Instantiates / Related Primes¶
The live Network Simplex Algorithm is a complete specialized solver of which a network pivot rule is a component; it is not a genus for ordinary-LP rules. Linear Programming (LP) names a model class. Selection is the closest broad operation, but its differential retained-output and complement roles are not constitutive to a rule specification, especially when only one move is eligible. Algorithm requires a complete procedure and inherits Iteration and Function Mapping commitments that belong to the surrounding solver rather than this next-move component. No directed parent currently passes an all-instance and ancestor test.
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 pivot-rule realization, not the whole family. Bland's finite Rule I uses an ordinal index instead of Devex's reported dynamic weighting. A complete network-simplex algorithm includes far more than its entering-arc rule. A generic graph ranking, criss-cross pivot system or complementarity pivot procedure should not be admitted here without the required feasible simplex state and legal update mapping.[3][1][2]
References¶
[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s
[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r
[3] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l
[4] 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. registry ↩a ↩b ↩c ↩d