Advances in Solving the Multicommodity-Flow Problem

The multicommodity-flow problem arises in a wide variety of important applications. Many communications, logistics, manufacturing, and transportation problems can be formulated as large multicommodity-flow problems. During the last few years researchers have made steady advances in solving extremely large multicommodity-flow problems. This improvement has been due both to algorithmic and to hardware advances. At present the primal simplex method using the basis-partitioning approach gives excellent solution times even on modest hardware. These results imply that we can now efficiently solve the extremely large multicommodity-flow models found in industry. The extreme-point solution can also be quickly reoptimized to meet the additional requirements often imposed upon the continuous solution. Currently practitioners are using EMNET, a primal basis-partitioning algorithm, to solve extremely large logistics problems with more than 600,000 constraints and 7,000,000 variables in the food industry.