An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems

Autor:	Jeff Kennington, Mohamed A. Shalaby
Rok vydání:	1977
Předmět:	Arc (geometry) Set (abstract data type) Mathematical optimization Heuristic (computer science) Strategy and Management Management Science and Operations Research Flow network Subgradient method Upper and lower bounds Matrix multiplication Multi-commodity flow problem Mathematics
Zdroj:	Management Science. 23:994-1004
ISSN:	1526-5501 0025-1909
DOI:	10.1287/mnsc.23.9.994
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f299fc036f33e897ebfbd2c22ecac918 https://doi.org/10.1287/mnsc.23.9.994 Zobrazit plný text záznamu Plný text ve formátu PDF