A Primal Simplex Approach to Pure Processing Networks

Pure processing network problems are minimum cost flow problems in which the flow entering or leaving a node may be constrained to do so in given proportions. In this paper, new theoretical results concerning pure processing networks are developed, and, based on these results, two new primal simplex variants are presented. One of these variants has been implemented and tested against a general purpose linear programming code. A large class of problems is identified for which the specialized code is an order of magnitude faster than the general purpose code.