ABSTRACT
The multicommodity flow problem is a generalization of the minimum cost flow problem, described in Chapter 5. Multicommodity flow problems are frequently encountered in several application domains. In many applications, several physical commodities, vehicles, or messages, each governed by their own network flow constraints, share the same network. For example, in telecommunications applications, telephone calls between specific node pairs in an underlying telephone network, each define a separate commodity, and all these commodities share common telephone line resources. In this chapter, we study the multicommodity flow problem, in which individual commodities share common arc capacities. That is, each arc has a capacity uij that restricts the total flow of all commodities on that arc. The objective
of this problem is to send several commodities that reside at one or more points in a network (sources or supplies) with arc capacities to one or more points on the network (sinks or demands), incurring minimum cost. The arc capacities bind the flows of all commodities together. If the commodities do not interact with each other (common arc capacities constraints are relaxed), then the multicommodity flow problem can be solved as several independent single commodity problems using the techniques discussed in Chapter 5. We now proceed to give the mathematical formulation of this problem.
