×

Solving network design problems via iterative aggregation. (English) Zbl 1327.90347

Summary: In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

Gurobi; SNDlib; DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Modern Phys. 74, 47-97 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[2] Balas, E.: Solution of large-scale transportation problems through aggregation. Oper. Res. 13(1), 82-93 (1965) · Zbl 0137.38502 · doi:10.1287/opre.13.1.82
[3] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[4] Chvátal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. In: Hammer, P., Johnson, E., Korte, B., Nemhauser, G. (eds.) Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, vol. 1, pp. 145-162. Elsevier (1977)
[5] Costa, A.M.: A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6), 1429-1450 (2005) · Zbl 1071.90009 · doi:10.1016/j.cor.2003.11.012
[6] Crainic, T.G., Frangioni, A., Gendron, B.: Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112, 73-99 (2001) · Zbl 1026.90010 · doi:10.1016/S0166-218X(00)00310-3
[7] Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS implementation challenge—shortest paths. http://www.dis.uniroma1.it/ challenge9/ (2006) · Zbl 1243.90006
[8] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Progr. A 91(2), 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[9] Dudkin, L., Rabinovich, I., Vakhutinsky, I.: Iterative aggregation theory. Number 111 in Pure and applied mathematics. Dekker, New York (1987)
[10] Fischetti, M., Salvagnin, D., Zanette, A.: A note on the selection of Benders’ cuts. Math. Progr. Series B 124, 175-182 (2010) · Zbl 1198.90302 · doi:10.1007/s10107-010-0365-7
[11] Francis, V.E.: Aggregation of network flow problems. Ph.D. thesis, University of California (1985) · Zbl 1049.90004
[12] Geisberger, R.: Advanced route planning in transportation networks. Ph.D. thesis, Karlsruhe Institute of Technology (2011)
[13] Gendron, B., Crainic, T.G., Frangioni, A.: Multicommodity capacitated network design. In: Soriano, P., Sansò, B. (eds.) Telecommunications network planning, vol. 98, pp. 1-19. Kluwer Academic Publishers (1998) · Zbl 1026.90010
[14] Geoffrion, A.; Balinski, M. (ed.), Lagrangean relaxation for integer programming, 82-114 (1974), Berlin · Zbl 0395.90056 · doi:10.1007/BFb0120690
[15] Gurobi Optimization, Inc.: Gurobi optimizer reference manual. http://www.gurobi.com (2013) · Zbl 1198.90302
[16] Hallefjord, A., Storoy, S.: Aggregation and disaggregation in integer programming problems. Oper. Res. 38(4), 619-623 (1990) · Zbl 0724.90045 · doi:10.1287/opre.38.4.619
[17] Hooker, J.N., Ottosson, G.: Logic-based Benders decomposition. Math. Progr. 96(1), 33-60 (2003) · Zbl 1023.90082
[18] Johnson, D.S., Lenstra, J.K., Kan, A.H.G.R.: The complexity of the network design problem. Networks 8(4), 279-285 (1978) · Zbl 0395.94048 · doi:10.1002/net.3230080402
[19] Karwan, M., Rardin, R.: Some relationships between lagrangian and surrogate duality in integer programming. Math. Progr. 17(1), 320-334 (1979) · Zbl 0421.90056 · doi:10.1007/BF01588253
[20] Lee, S.: Surrogate programming by aggregation. Ph.D. thesis, University of California (1975) · Zbl 1219.90022
[21] Leisten, R.: Iterative Aggregation und Mehrstufige Entscheidungsmodelle: Einordnung in Den Planerischen Kontext, Analyse Anhand Der Modelle Der Linearen Programmierung und Darstellung Am Anwendungsbeispiel Der Hierarchischen Produktionsplanung. Produktion Und Logistik. Physica (1995) · Zbl 1026.90010
[22] Leisten, R.: An LP-aggregation view on aggregation in multi-level production planning. Ann. Oper. Res. Bd. 82, S.413-S.434 (1998) · Zbl 0911.90186 · doi:10.1023/A:1018931224060
[23] Lemaréchal, C.; Jünger, M. (ed.); Naddef, D. (ed.), Lagrangian relaxation, 112-156 (2001), Berlin · Zbl 1052.90065
[24] Linderoth, J., Margot, F., Thain, G.: Improving bounds on the football pool problem by integer programming and high-throughput computing. INFORMS J. Comput. 21(3), 445-457 (2009) · Zbl 1243.90006 · doi:10.1287/ijoc.1090.0334
[25] Litvinchev, I., Tsurkov, V.: Aggregation in large-scale optimization. In: Applied optimization, vol. 83. Springer (2003) · Zbl 1029.90042
[26] Macedo, R., Alves, C., de Carvalho, J.V., Clautiaux, F., Hanafi, S.: Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur. J. Oper. Res. 214(3), 536-545 (2011) · Zbl 1219.90022 · doi:10.1016/j.ejor.2011.04.037
[27] McDaniel, D., Devine, M.: A modified Benders’ partitioning algorithm for mixed integer programming. Manag. Sci. 24(3), 312-319 (1977) · Zbl 0371.90102 · doi:10.1287/mnsc.24.3.312
[28] Newman, A.M., Kuchta, M.: Using aggregation to optimize long-term production planning at an underground mine. Eur. J. Oper. Res. 176(2), 1205-1218 (2007) · Zbl 1103.90333 · doi:10.1016/j.ejor.2005.09.008
[29] Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0-Survivable Network Design Library. In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007). Spa, Belgium (2007)
[30] Rogers, D.F., Plante, R.D., Wong, R.T., Evans, J.R.: Aggregation and disaggregation techniques and methodology in optimization. Oper. Res. 39(4), 553-582 (1991) · Zbl 0729.90738 · doi:10.1287/opre.39.4.553
[31] Rosenberg, I.: Aggregation of equations in integer programming. Discrete Math. 10(2), 325-341 (1974) · Zbl 0297.90054 · doi:10.1016/0012-365X(74)90126-5
[32] Salvagnin, D.; Walsh, T.; Milano, M. (ed.), A hybrid MIP/CP approach for multi-activity shift scheduling, 633-646 (2012), Berlin · doi:10.1007/978-3-642-33558-7_46
[33] Zipkin, P.H.: Aggregation in linear programming. Ph.D. thesis, Yale University (1977) · Zbl 0297.90054
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.