A multicommodity network-flow problem with side constraints on paths solved by column generation

A multicommodity network-flow problem with side constraints on paths solved by column generation

0.00 Avg rating0 Votes
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: ,
Keywords: networks: flow, programming: integer
Abstract:

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 NP-hard with the constrained shortest-path problem as a special case. To solve the extended model, we use a column-generation approach, in which the solution is built up successively by path generation. The side constraints are efficiently handled in the path-generation subproblem. We further discuss various enhancements of this approach. Computational results show that the column-generation approach provides an efficient way for solving the extended model, even for fairly large networks.

Reviews

Required fields are marked *. Your email address will not be published.