Models and algorithms for network reduction

Gang Li

doi:10.1016/j.ejor.2015.08.008

2016-02-01

PRE

李

李纲 (Gang Li) *

Anantaram Balakrishnan

DOI：10.1016/j.ejor.2015.08.008

原文链接

原文求助

摘要

En 中文

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. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

Keyword:

Networks

Large scale optimization

Heuristics

Shortest path

Dual ascent