Models and algorithms for network reduction

Gang Li and Anantaram Balakrishnan

European Journal of Operational Research, 2016, vol. 248, issue 3, 930-942

Abstract: We study models and algorithms for a Network Reduction (NR) problem that entails constructing a reduced network in place of an existing large network so that the shortest path lengths between specified node pairs in this network are equal to or only slightly longer than the corresponding shortest path lengths in the original network. Solving this problem can be very useful both to accelerate shortest path calculations in many practical contexts and to reduce the size of optimization models that contain embedded shortest path problems. This work was motivated by a real problem of scheduling and routing resources to perform spatially dispersed jobs, but also has other applications. We consider two variants of the NR problem—a Min-Size NR problem that minimizes the number of arcs in the reduced network while ensuring that the shortest path lengths in this network are close to the original lengths, and a Min-Length NR problem that minimizes a weighted sum of shortest path lengths over all the specified node pairs while limiting the number of arcs in the reduced network. We model both problems as integer programs with multi-commodity flows, and propose optimization-based heuristic algorithms to solve them. These methods include preprocessing, a shortest path-based procedure with local improvement, and a dual ascent algorithm. We report on the successful applications to reduce the network for practical infrastructure project planning and to condense a transportation network for distribution planning. We also compare these solutions with those obtained using algorithms for minimum length trees.

Keywords: Networks; Large scale optimization; Heuristics; Shortest path; Dual ascent (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715007250
Full text for ScienceDirect subscribers only

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:eee:ejores:v:248:y:2016:i:3:p:930-942

DOI: 10.1016/j.ejor.2015.08.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().