Capacitated Network Design: Exact Algorithms, Reformulations and the Convex Hull

Sastry Trilochan

No WP1998-10-04, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: We study exact algorithms for several variations of the capacitated network design problem, all of which are known to be NP-hard. Exact algorithms are useful for telecommunication network design since the cost of installing networks is very high, and optimal solutions could provide substantial cost savings compared to heuristic solutions. We describe an O(n22n) implicit tree enumeration algorithm and an O(n22k+n3k) dynamic programming path based algorithm where n is the number of nodes and K the number of terminals that need to be connected. In general, the worst case running times of the two algorithms are the same for capacitated and uncapacitated problems, and surprisingly, are faster for problem instances where the capacity constraint on edges is very tight. We also describe the convex hull of feasible integer solutions using O(m2k+n3k) variables and O(n2k) constraints, which is polynomial for fixed K. Finally we show how to use these algorithms to solve a wide variety of related problems, including those with node capacities, the concentrator locator and capacitated plant location problems, a variant of the network loading problem, network expansion, i.e., adding nodes and edges to an existing network, the two level network design problem, and the problem of long term planning where the network is expanded over several years.

Date: 1998-10-04
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:iim:iimawp:wp01557

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().