Implementation of a Combinatorial Multicommodity Flow Algorithm.

The multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total amount of flow on each edge is no more than the capacity of the edge. This problem can be expressed as a large linear program, and most known algorithms for it, both theoretical and practical, are linear programming algorithms designed to take advantage of the structure of multicommodity flow problems. The size of the linear programs, however, makes it prohibitively difficult to solve large multicommodity flow problems. In this paper, we describe and examine a multicommodity flow implementation based on the recent combinatorial approximation algorithm of Leighton, et al. The theory predicts that the running time of the algorithm increases linearly with the number of commodities. Our experiments verify this behavior. The theory also predicts that the running time increases as the square of the desired precision. Our experiments show that the running time increases at most this fast, and often slower. We also compare our combinatorial implementation against a linear programming-based code of Kennington which is known to perform well on multicommodity flow problems. For many problems, our combinatorial algorithm outperforms the linear programming-based algorithm. More precisely, as the number of commodities increases, the running time of our algorithm grows much more slowly than that of Kennington's linear programming-based algorithm. Our results suggest that our algorithm can solve larger multicommodity flow problems than have been solved in the past.