A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design

A. Balakrishnan, T. L. Magnanti and R. T. Wong
Additional contact information
A. Balakrishnan: Massachusetts Institute of Technology, Cambridge, Massachusetts
T. L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
R. T. Wong: Purdue University, West Lafayette, Indiana

Operations Research, 1989, vol. 37, issue 5, 716-740

Abstract: The fixed-charge network design problem arises in a variety of problem contexts including transportation, communication, and production scheduling. We develop a family of dual-ascent algorithms for this problem. This approach generalizes known ascent procedures for solving shortest path, plant location, Steiner network and directed spanning tree problems. Our computational results for several classes of test problems with up to 500 integer and 1.98 million continuous variables and constraints show that the dual-ascent procedure and an associated drop-add heuristic generate solutions that, in almost all cases, are guaranteed to be within 1 to 4% of optimality. Moreover, the procedure requires no more than 150 seconds on an IBM 3083 computer. The test problems correspond to dense and sparse networks, including some models that arise in freight transport.

Keywords: networks/graphs; flow algorithms: dual-ascent for fixed charge network flow; programming; integer: algorithm for uncapacitated network design; transportation; freight: network design model and algorithm (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.5.716 (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:oropre:v:37:y:1989:i:5:p:716-740

Access Statistics for this article

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