Decisions, Operations, and Technology Management

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 objective 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.