Solving the undirected multicommodity flow problem using a shortest path-based pricing algorithm

The undirected multicommodity flow problem is encountered in the solution to traffic-scheduling problems related to computer, communication, railroad, and other networks. We show how to formulate this problem as a piecewise linear optimization problem (with piecewise linear convex functions in both the obejctive and the constraints). We discuss how EMNET, a primal basis partitioning simplex algorithm, was modified so as to efficiently solve these problems using a pricing procedure that we call shortest path pricing. Extremely good solution times for some very large problems are presented. The solutions are not only obtained quickly, but also with a fraction of the number of pivots that are needed for the standard simplex method.