Dual‐ascent methods for large‐scale multicommodity flow problems

Cynthia Barnhart

Naval Research Logistics (NRL), 1993, vol. 40, issue 3, 305-324

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

Date: 1993
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199304)40:33.0.CO;2-4

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:wly:navres:v:40:y:1993:i:3:p:305-324

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().