An Algorithm for Solving Network Problems with Side Variables

Many algorithms for network linear programming problems with non-network (side) variables maintain a working basis for the basic side variables and a tree or forest data structure for the basic network (arc) variables. We present a new variation on this theme of primal basis partitioning. In this algorithm the spanning tree maintained to facilitate the workings of the simplex method is not necessarily the basis. This spanning tree contains all the basic arc variables and many nonbasic arc variables as there are basic side variables. Instead of a working basis, the algorithm maintains a matrix which connects the spanning tree with the current basis. The method presented is a more natural extension of the pure network simplex method.