Another simplex-type method for large scale linear programming

A method is proposed for solving large sparse linear programs. Unlike the well-known simplex method (that makes steps along the edges of polyhedron), the method analysed in this paper takes steps in the directions that belong to the faces of feasible region or cross its interior. More freedom is thus left in their choice. A few remarks concerning the method's implementation are also made. The revised version of the method extensively uses the notion of working basis, a nonsingular submatrix of the active part of LP constraint matrix. Throughout the major part of optimization process working basis has size remarkably smaller than the number of constraints, which is beneficial for the efficiency of the method. An experimental implementation of the method is shown to compare favorably with the simplex and primal–dual interior point codes on large set of real-life Netlib test problems.