Note—A Note on the Criss-Cross Algorithm

The “Criss-cross” linear programming method formulated by Zionts (Zionts, Sanley. 1969. The criss-cross method for solving linear programming problems. Management Sci.15 (7, March) 426–445.), although remarkably efficient for small problems (Zionts [Zionts, Sanley. 1972. Some empirical tests of the criss-cross method. Management Sci.19 (4, December) 406–410.]), often requires an excessive number of iterations for problems of size 40 × 40 or larger. Garfinkel and Yu (Garfinkel, Robert S., P. L. Yu. 1974. The composite simplex algorithm. Paper MA10.4. Joint National ORSA/TIMS Meeting, Boston, 22 April.) reported 3 such problems for which it terminated short of solution after 1000 pivots. Fortunately, the algorithm can be salvaged. All that is needed is a minor pivot rule change.