An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems

Jeff Kennington and Mohamed Shalaby
Additional contact information
Jeff Kennington: Southern Methodist University
Mohamed Shalaby: Southern Methodist University

Management Science, 1977, vol. 23, issue 9, 994-1004

Abstract: 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.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.23.9.994 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:23:y:1977:i:9:p:994-1004

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().