Browse Prior Art Database

Nondegenerate Simplex Method Rule

IP.com Disclosure Number: IPCOM000068651D
Original Publication Date: 1978-Jan-01
Included in the Prior Art Database: 2005-Feb-20

Publishing Venue

IBM

Related People

Authors:
Crowder, HP Wolfe, PS [+details]

Abstract

In [1] Robert Bland has given a simple rule for pivoting in the simplex method which makes cycling due to degeneracy impossible. ([1] actually discusses two rules, we speak here only of his "Rule I".) It is easily stated: let all the variables of the problem be ordered with distinct priorities. The pivot column for a simplex-method pivot is chosen as that corresponding to the nonbasic variable having highest priority among all those with negative reduced costs, and among all candidates for choice of pivot row (which must be chosen so as to maintain feasibility), that row corresponding to the basic variable of highest priority is chosen. This rule also has a simple proof of its effectiveness.