Solving Multicommodity Flow Problems with a Primal Embedded Network Simplex Algorithm

This article describes the authors’ experience solving large multicommodity flow problems with an embedded network simplex algorithm augmented with a fast-start heuristic for choosing an initial basis. The heuristic makes successive capacity allocations in an attempt to find a feasible initial basis. Our implementation of the heuristic makes use of piece-wise linear convex costs. The efficacy of our heuristic, and of the embedded network simplex method, is demonstrated on large publicly available multicommodity flow problems. Comparisons with other published computational results are given.