A complementary pivoting algorithm for linear network problems

In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal, and Schneider for solving singlecommodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in which a sequence of subproblems is formed by solving the problem ‘one-node-at-a-time’. The algorithm is tested on uncapacitated transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm is implemented in C under UNIX), the results show that the method is very effective and may be competitive with the best available algorithms for linear network problems. This research was supported, in part, by grant number ECS-8504195 from the National Science Foundation.