×

Models and algorithms for network reduction. (English) Zbl 1346.90222

Summary: 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.

MSC:

90B10 Deterministic network models in operations research
90C10 Integer programming
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: Theory, algorithms, and applications (1993), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey · Zbl 1201.90001
[2] Ahuja, R. K.; Murty, V. V.S., Exact and heuristic algorithms for the optimum communication spanning tree problem, Transportation Science, 21, 3, 163-170 (1987) · Zbl 0624.90026
[3] Allan, D.; Bragg, N., 802.1aq shortest path bridging design and evolution: The architect’s perspective (2012), John Wiley Sons, Inc: John Wiley Sons, Inc Hoboken, New Jersey
[4] Alon, N.; Karp, R. M.; Peleg, D.; West, D., A graph theoretic game and its application to the k-server problem, SIAM Journal on Computing, 24, 1, 78-100 (1995) · Zbl 0818.90147
[5] Balakrishnan, A.; Geunes, J.; Pangburn, M. S., Coordinating the distribution chain: New models for new challenges, Supply chain management: Models, applications, and research directions, 199-242 (2002), Kluwer Academic Publishers · Zbl 1050.90512
[6] Balakrishnan, A.; Magnanti, T. L.; Wong, R. T., A dual-ascent procedure for large-scale uncapacitated network design, Operations Research, 37, 5, 716-740 (1989) · Zbl 0681.90083
[7] Balakrishnan, A.; Patel, N. R., Problem reduction methods and a tree generation algorithm for the Steiner Network problem, Networks, 17, 65-85 (1987) · Zbl 0643.90090
[8] Barnhart, C.; Jin, H.; Vance, P. H., Railroad blocking: A network design application, Operations Research, 48, 4, 603-614 (2000)
[9] Berman, P.; Bhattacharyya, A.; Makarychev, K.; Raskhodnikova, S.; Yaroslavtsev, G., Improved approximation for the directed spanner problem, Automata, languages and programming, 1-12 (2011), Springer: Springer Berlin · Zbl 1332.68283
[10] Bilde, O.; Krarup, J., Sharp lower bounds and efficient algorithms for the simple plant location problem, Annals of Discrete Mathematics, 1, 1, 79-97 (1977)
[11] Bardossy, M. G.; Raghavan, S., Dual-based local search for the connected facility location and related problems, INFORMS Journal on Computing, 22, 4, 584-602 (2010) · Zbl 1243.90085
[12] Bein, W. W.; Kamburowski, J.; Stallmann, M. F., Optimal reduction of two-terminal directed acyclic graphs, SIAM Journal on Computing, 21, 6, 1112-1129 (1992) · Zbl 0768.68119
[13] Borgwardt, S.; Schmiedl, F., Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem, European Journal of Operational Research, 234, 3, 631-640 (2014) · Zbl 1304.68210
[14] Campos, R.; Ricardo, M., A fast algorithm for computing minimum routing cost spanning trees, Computer Networks, 52, 17, 3229-3247 (2008) · Zbl 1152.68325
[15] Chardy, M.; Costa, M. C.; Faye, A.; Trampont, M., Optimizing splitter and fiber location in a multilevel optical FTTH network, European Journal of Operational Research, 222, 3, 430-440 (2012) · Zbl 1253.90132
[16] Chou, H.; Premkumar, G.; Chu, C. H., Genetic algorithms for communications network design - An empirical study of the factors that influence performance, IEEE Transactions on Evolutionary Computation, 5, 3, 236-249 (2001)
[17] Cowen, L., Compact routing with minimum stretch, Journal of Algorithms, 38, 1, 170-183 (2001) · Zbl 0969.68180
[18] Crainic, T. G., Service network design in freight transportation, European Journal of Operational Research, 122, 2, 272-288 (2000) · Zbl 0961.90010
[19] Demir, E.; Bektaş, T.; Laporte, G., A review of recent research on green road freight transportation, European Journal of Operational Research, 237, 3, 775-793 (2014) · Zbl 1338.90004
[20] Elkin, M.; Peleg, D., The hardness of approximating spanner problems, Theory of Computing Systems, 41, 4, 691-729 (2007) · Zbl 1148.68024
[21] Elkin, M.; Zhang, J., Efficient algorithms for constructing (1+ ε, β)-spanners in the distributed and streaming models, Distributed Computing, 18, 5, 375-385 (2006) · Zbl 1266.68212
[22] Erlenkotter, D., A dual based procedure for uncapacitated facility location, Operations Research, 26, 6, 992-1009 (1978) · Zbl 0422.90053
[23] Fischer, T.; Merz, P., A memetic algorithm for the optimum communication spanning tree problem, Hybrid Metaheuristics, 170-184 (2007), Springer: Springer Berlin
[24] Fischetti, M.; Lancia, G.; Serafini, P., Exact algorithms for minimum routing cost trees, Networks, 39, 3, 161-173 (2002) · Zbl 1027.90103
[25] Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Management Science, 27, 1, 1-18 (1981) · Zbl 0466.90054
[26] Fu, L.; Sun, D.; Rilett, L. R., Heuristic shortest path algorithms for transportation applications: State of the art, Computers & Operations Research, 33, 11, 3324-3343 (2006) · Zbl 1113.90034
[27] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039
[28] Gendron, B., A note on “a dual-ascent approach to the fixed-charge capacitated network design problem”, European Journal of Operational Research, 138, 3, 671-675 (2002) · Zbl 1003.90004
[29] Goczyła, K.; Cielatkowski, J., Optimal routing in a transportation network, European Journal of Operational Research, 87, 2, 214-222 (1995) · Zbl 0914.90106
[30] Herrmann, J. W.; Ioannou, G.; Minis, I.; Proth, J. M., A dual-ascent approach to the fixed-charge capacitated network design problem, European Journal of Operational Research, 95, 3, 476-490 (1996) · Zbl 0943.90501
[31] Hu, T. C., Optimum communication spanning trees, SIAM Journal on Computing, 3, 3, 188-195 (1974) · Zbl 0269.90010
[32] Johnson, S.; Lenstra, J. K.; Rinnooy Kan, A. H.G., The complexity of the network design problem, Networks, 8, 4, 279-285 (1978) · Zbl 0395.94048
[33] Kortsarz, G.; Peleg, D., Generating sparse 2-spanners, Journal of Algorithms, 17, 2, 222-236 (1994) · Zbl 1427.68246
[34] Li, F.; Klette, R., Euclidean shortest paths: Exact or approximate algorithms (2011), Springer: Springer London · Zbl 1263.68008
[35] Li, F.; Cheng, D.; Hadjieleftheriou, M.; Kollios, G.; Teng, S. H., On trip planning queries in spatial databases, Advances in spatial and temporal databases, 273-290 (2005), Springer: Springer Berlin
[36] Li, G., Optimization-based decision support for inspection and maintenance of infrastructure networks (2011), University of Texas at Austin, (Ph.D. dissertation)
[37] Li, Y.; Bouchebaba, Y., A new genetic algorithm for the optimal communication spanning tree problem, (Fonlupt, C.; Hao, J.-K.; Lutton, E.; Ronald, E.; Schoenauer, M., Proceedings of artificial evolution: Fifth European conference (1999), Springer: Springer Berlin), 162-173 · Zbl 0966.68552
[38] Magnanti, T. L.; Wong, R. T., Network design and transportation planning: Models and algorithms, Transportation Science, 18, 1, 1-55 (1984)
[39] Narasimhan, G.; Smid, M., Geometric spanner networks (2007), Cambridge University Press: Cambridge University Press New York · Zbl 1140.68068
[40] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1988), Wiley Interscience: Wiley Interscience New York · Zbl 0469.90052
[41] Peleg, D.; Schaffer, A., Graph spanners, Journal of Graph Theory, 13, 1, 99-116 (1989) · Zbl 0673.05059
[42] Peleg, D.; Reshef, E., Deterministic polylog approximation for minimum communication spanning trees, Lecture notes in computer science, 670-682 (1998), Springer: Springer Berlin
[43] Sharma, P., Algorithms for the optimum communication spanning tree problem, Annals of Operations Research, 143, 1, 203-209 (2006) · Zbl 1101.90058
[44] SteadieSeifi, M.; Dellaert, N. P.; Nuijten, W.; Van Woensel, T.; Raoufi, R., Multimodal freight transportation planning: A literature review, European Journal of Operational Research, 233, 1, 1-15 (2014) · Zbl 1339.90008
[45] Tavares, L. V., A review of the contribution of operational research to project management, European Journal of Operational Research, 136, 1, 1-18 (2002) · Zbl 1086.90532
[46] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Heuristics for multi-attribute vehicle routing problems: A survey and synthesis, European Journal of Operational Research, 231, 1, 1-21 (2013) · Zbl 1317.90006
[47] Wong, R. T., Worst-case analysis of network design problem heuristics, SIAM Journal of Algebraic Discrete Mathematics, 1, 1, 51-63 (1980) · Zbl 0498.90032
[48] Wong, R. T., Dual ascent approach for Steiner tree problems on a directed graph, Mathematical Programming, 28, 3, 271-287 (1984) · Zbl 0532.90092
[49] Wu, B. Y.; Chao, K. M.; Tang, C. Y., Approximation algorithms for some optimum communication spanning tree problems, Discrete Applied Mathematics, 102, 3, 245-266 (2000) · Zbl 0957.68088
[50] Wu, B. Y.; Chao, K. M.; Tang, C. Y., Approximation algorithms for the shortest total path length spanning tree problem, Discrete Applied Mathematics, 105, 1, 273-289 (2000) · Zbl 0958.05024
[51] Wu, B. Y.; Lancia, G.; Bafna, V.; Chao, K. M.; Ravi, R.; Tang, C. Y., A polynomial time approximation scheme for minimum routing cost spanning trees, SIAM Journal on Computing, 29, 3, 761-778 (2000) · Zbl 0941.68159
[52] Wu, B. Y., Approximation algorithms for the optimal p-source communication spanning tree, Discrete Applied Mathematics, 143, 1, 31-42 (2004) · Zbl 1055.05145
[53] Yoon, M.-G.; Current, J., The hub location and network design problem with fixed and variable arc costs: Formulation and dual-based solution heuristic, Journal of the Operational Research Society, 59, 1, 80-89 (2008) · Zbl 1166.90355
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.