Premium
Dual‐ascent methods for large‐scale multicommodity flow problems
Author(s) -
Barnhart Cynthia
Publication year - 1993
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199304)40:3<305::aid-nav3220400303>3.0.co;2-4
Subject(s) - multi commodity flow problem , mathematical optimization , heuristics , generator (circuit theory) , mathematics , dual (grammatical number) , scale (ratio) , heuristic , flow network , flow (mathematics) , computer science , art , geometry , literature , power (physics) , physics , quantum mechanics
The capacitated multicommodity network flow problem presents itself in a number of problem contexts including transportation, communication, and production. To solve the large‐scale multicommodity flow problems encountered in these fields, we develop dual‐ascent heuristics and a primal solution generator. The dual‐ascent solutions, in addition to determining lower bounds on the optimal objective function value, provide advanced starting solutions for use with primal‐based solution techniques. The primal solution generator uses the dual‐ascent solution to obtain heuristically primal solutions to the multicommodity flow problems. Computational experiments performed on three test problem sets show that the dual‐ascent and primal heuristic procedures typically determine nearoptimal solutions quickly. In addition, by using the dual‐ascent procedure to obtain advanced starting solutions, run times for optimal multicommodity flow procedures are reduced significantly and greatly improved solutions are obtained by the new primal solution generator. © 1993 John Wiley & Sons, Inc.