A network simplex method

Simple combinatorial modifications are given which ensure finiteness in the primal simplex method for the transshipment problem and the upper-bounded primal simplex method for the minimum cost flow problem. The modifications involve keeping strongly feasible bases. An efficient algorithm is given for converting any feasible basis into a strongly feasible basis. Strong feasibility is preserved by a rule for choosing the leaving basic variable at each simplex iteration. The method presented is closely related to a new perturbation technique and to previously known degeneracy modifications for shortest path problems and maximum flow problems.The author holds a National Research Council of Canada Post-Doctorate Fellowship.