A Primal Simplex Specialization for the Equal Flow Problem

Abstract

This paper presents a primal simplex specialization for the equal flow problem. This approach is motivated by a desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The simplex computations are discussed and a starting solution based on the subgradient optimization technique is presented. Our implementation is tested on problems with up to 1500 nodes, 6600 arcs and 600 equal flow pairs. These problems are also solved using MPSX and another specialized code for the equal flow problem. We present Computational experience which indicates that our approach is well suited for problems with up to 150 side constraints. As the number of pairs increased, MPSX with an advanced start procedure, performed better than our specialized code.