An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems

This paper presents a heuristic technique for obtaining good solutions to large multicommodity network flow problems. The general approach is to allocate the arc capacities among the individual commodities and hence decompose the problem into a set of one-commodity problems. The one-commodity problems are solved and the combined solution is compared to a lower bound. If the solution is within an acceptable deviation from the lower bound, the procedure terminates. Otherwise, the arc capacities are reallocated and the subprograms are resolved. The reallocation is based on a subgradient optimization approach. Hence, the heuristic technique involves no matrix operations which may lead to round-off errors, the storage requirements are modest, and almost all operations are carried out directly on one-commodity networks. The technique has been coded and the initial computational experience is encouraging.

• 저널Management Science · 23(9) · 994–1004
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.23.9.994
• 저자Jeff Kennington, Mohamed A. Wahby Shalaby