Article ID: | iaor2004404 |
Country: | United States |
Volume: | 15 |
Issue: | 1 |
Start Page Number: | 42 |
End Page Number: | 57 |
Publication Date: | Jan 2003 |
Journal: | INFORMS Journal On Computing |
Authors: | Holmberg Kaj, Yuan Di |
Keywords: | networks: flow, programming: integer |
The multicommodity network-flow model concerns routing of a number of commodities through a capacitated network at minimal cost. In the basic model, it is assumed that for each commodity, the flow can be routed on any path connecting its origin and its destination. In telecommunication applications, where a commodity represents a communication pair, there are often additional time-delay or reliability requirements on paths that are used for routing. These requirements may vary by communication pair, represented by different priority classes. In this paper, we extend the basic multicommodity network-flow model to include such side constraints on paths. The extended problem is