Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound

Kaj Holmberg and Johan Hellstrand
Additional contact information
Kaj Holmberg: Linköping Institute of Technology, Linköping, Sweden
Johan Hellstrand: Linköping Institute of Technology, Linköping, Sweden

Operations Research, 1998, vol. 46, issue 2, 247-259

Abstract: The network design problem is a multicommodity minimal cost network flow problem with fixed costs on the arcs, i.e., a structured linear mixed-integer programming problem. It has various applications, such as construction of new links in transportation networks, topological design of computer communication networks, and planning of empty freight car transportation on railways. We present a Lagrangean heuristic within a branch-and-bound framework as a method for finding the exact optimal solution of the uncapacitated network design problem with single origins and destinations for each commodity (the simplest problem in this class, but still NP-hard). The Lagrangean heuristic uses a Lagrangean relaxation as subproblem, solving the Lagrange dual with subgradient optimization, combined with a primal heuristic (the Benders subproblem) yielding primal feasible solutions. Computational tests on problems of various sizes (up to 1000 arcs, 70 nodes and 138 commodities or 40 nodes and 600 commodities) and of several different structures lead to the conclusion that the method is quite powerful, outperforming for example a state-of-the-art mixed-integer code, both with respect to problem size and solution time.

Keywords: Programming; integer; algorithms; relaxation/subgradient; branch-and-bound; Networks/graphs; multicommodity; fixed charges (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.2.247 (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:46:y:1998:i:2:p:247-259

Access Statistics for this article

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