Multicommodity Network Problems: Applications and Computations

It is well documented that pure network problems can be solved from 10 to 100 times faster using specialized primal simplex software as compared to general linear programming systems. For multi-commodity network flow problems, the computational savings are a function of the number of tight-side constraints. In this study, we present three real-world multicommodity models and data concerning the number of tight-side constraints. We also present the results of a computational study on a set of 25 randomly generated test problems which have a wide range of number of tight-side constraints. We conclude that a specialized multicommodity network code is three times as fast as a general code, while a specialized network with general side constraints code has twice the speed of a general LP code.