Theoretical Properties of the Network Simplex Method

Abstract

An example of cycling in the network simplex method is given and some restrictions on its occurrence are proved. An example of “stalling” (an exponentially long sequence of consecutive degenerate pivots without cycling) is also given, and two methods which prevent cycling are shown to admit stalling. Pivoting rules which prevent the occurrence of both cycling and stalling are described, and some computational advantages are noted. Related results for the upper-bounded and dual simplex methods are also described.