Reliable Network Design Problem under Node Failure with Benders Decomposition

Tie Liu, Wenguo Yang, Jun Huang

College of Engineering, University of Chinese Academy of Sciences, Beijing, China.
School of Mathematics Sciences, University of Chinese Academy of Sciences, Beijing, China.

DOI: 10.4236/am.2014.52026                

Abstract

The design of telecommunication network with capacity constraints of links, routers and ports of routers is considered in this paper. Specially, we limit each demand flow traversed through a pre-specified maximal number of links (called hops) under node failure scenarios in IP layer network. Such a design must be the most cost-effective and ensure that feasible flows continue to exist even when any relay node of the network fails. We propose a reliable mixed-integer programming (MIP) model with multi-scenario constraints to optimally design a minimum-cost survivable IP network that continues to support a good communication under any node failure scenario. Then we transform the MIP model into many single scenario models, that is, simplified MIPs, nonlinear programming (NLP) models and MIP models under Benders decomposition Then we transform the MIP model into many single scenario models, that is, simplified MIPs, nonlinear programming (NLP) models and MIP models under Benders decomposition. Three heuristic methods are proposed to solve these models including branch-and-bound algorithm, global algorithm for NLP, and heuristic algorithm based on benders decomposition. We mainly study the application of Benders decomposition method, where dual model and bounding procedures are given for each MIP model under Benders decomposition at each scenario. The results of our computational experiments validate the effectiveness of the proposed models and algorithms.

Keywords

Mixed-Integer Programming; Benders Decomposition; Network Design; Node Failure

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Minoux, “Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications,” Network, Vol. 19, No. 3, 1989, pp. 313-360.
[2]	S. Alumur and Bahar Y. Kara, “Network Hub Location Problems: The State of the Art,” European Journal of Operational Research, Vol. 190, No. 1, 2008, pp. 1-21.
[3]	M. Abd-El-Barr, “Topological Network Design: A Survey,” Journal of Network and Computer Applications, Vol. 32, No. 3, 2009, pp. 501-509. http://dx.doi.org/10.1016/j.jnca.2008.12.001
[4]	S. Soni, H. Pirkul and R. Gupta, “Survivable Network Design: The State of the Art,” Information Systems Frontiers, Vol. 1, No. 3, 1999, pp. 303-315. http://dx.doi.org/10.1023/A:1010058513558
[5]	H. Kerivin and A. R. Mahjoub, “Design of Survivable Networks: A Survey,” Research Report LIMOS/RR-05-04, 2005, pp. 1-21.
[6]	M. Garg and J. C. Smith, “Models and Algorithms for the Design of Survivable Multi-Commodity Flow Networks with General Failure Scenarios,” Omega, Vol. 36, No. 6, 2008, pp. 1057-1071. http://dx.doi.org/10.1016/j.omega.2006.05.006
[7]	S. Orlowski, “Local and Global Restoration of Node and Link Failures in Telecommunication Networks,” Master’s Thesis, Fachbereich Mathematik der TU, Berlin, 2003.
[8]	J. Desai and S. Sen, “A Global Optimization Algorithm for Reliable Network Design,” European Journal of Operational Research, Vol. 200, No. 1, 2010, pp. 1-8. http://dx.doi.org/10.1016/j.ejor.2008.12.016
[9]	T. Liu, W. G. Yang, J. X. Liao and J. Huang, “Robust Optimization for Designing Reliable Telecommunication Networks with Node Failure Scenarios,” 2010 IEEE International Conference on Emergency Management and Management Sciences (ICEMMS 2010), pp. 218-221.
[10]	C. G. Gruber, et al., “A New Model and a Computational Study for Demand-Wise Shared Protection,” Berlin-Dahlem, ZIBReport, 2005, p. 55.
[11]	R. Hulsermann, et al., “Availability and Cost Based Evaluation of Demand-Wise Shared Protection,” Berlin-Dahlem, ZIBReport, 2006, p. 15.
[12]	E. Rosenberg, “Hierarchical Topological Network Design,” IEEE/ACM Transactions on Networking, 2005, pp. 1402-1409. http://dx.doi.org/10.1109/TNET.2005.860100
[13]	S. Soni, “Hop Constrained Network Design Problem with Partial Survivability,” Annals of Operations Research, Vol. 106, No. 1-4, 2001, pp. 181-198. http://dx.doi.org/10.1023/A:1014513809519
[14]	A. Balakrishnan and K. Altinkemer, “Using a Hop-Constrained Model to Generate Alternative Communication Network Design,” ORSA Journal on Computing, Vol. 4, No. 2, 1992, pp. 192-205. http://dx.doi.org/10.1287/ijoc.4.2.192
[15]	R. Andrade, A. Lisser, N. Maculan and G. Platfau, “Telecommunication Network Capacity Design for Uncertain Demand,” Computational Optimization and Applications, Vol. 29, No. 2, 2004, pp. 127-146. http://dx.doi.org/10.1023/B:COAP.0000042027.65400.b3
[16]	O. E. Flippo, A. W. J. Kolen, et al., “A Dynamic Programming Algorithm for the Local Access Telecommunication Network Expansion Problem,” European Journal of Operational Research, Vol. 127, No. 1, 2000, pp. 189-202. http://dx.doi.org/10.1016/S0377-2217(99)00340-9
[17]	M. Riis and K. A. Andersen, “Multi-Period Capacity Expansion of a Telecommunications Connection with Uncertain Demand,” Computers & Operations Research, Vol. 31, No. 9, 2004, pp. 1427-1436. http://dx.doi.org/10.1016/S0305-0548(03)00098-4
[18]	A. Atamtürk and M. Zhang, “Two-Stage Robust Network Flow and Design under Demand Uncertainty,” Operations Research, Vol. 55, No. 4, 2007, pp. 662-673. http://dx.doi.org/10.1287/opre.1070.0428
[19]	Y. F. Yin, S. M. Madanat and X.-Y. Lu, “Robust Improvement Schemes for Road Networks under Demand Uncertainty,” European Journal of Operational Research, Vol. 198, No. 2, 2009, pp. 470-479. http://dx.doi.org/10.1016/j.ejor.2008.09.008
[20]	S. E. Terblanche, R. Wessaly and J. M. Hattingh, “Survivable Network Design with Demand Uncertainty,” European Journal of Operational Research, Vol. 210, No. 1, 2011, pp. 10-26. http://dx.doi.org/10.1016/j.ejor.2010.09.041
[21]	A. L. Soyster, “Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming,” Operations Research, Vol. 21, No. 5, 1973, pp. 1154-1157. http://dx.doi.org/10.1287/opre.21.5.1154
[22]	E. A. Cabral, E. Erkut, G. Laporte and R. A. Patterson, “The Network Design Problem with Relays,” European Journal of Operational Research, Vol. 180, No. 2, 2007, pp. 834-844. http://dx.doi.org/10.1016/j.ejor.2006.04.030
[23]	I. Rodríguez-Martín and J. J. Salazar-González, “Solving a Capacitated Hub Location Problem,” European Journal of Operational Research, Vol. 184, No. 2, 2008, pp. 468-479. http://dx.doi.org/10.1016/j.ejor.2006.11.026
[24]	I. Contreras, J. A. Díaz and E. Fernández, “Lagrangean Relaxation for the Capacitated Hub Location Problem with Single Assignment,” OR Spectrum, Vol. 31, No. 3, 2009, pp. 483-505. http://dx.doi.org/10.1007/s00291-008-0159-y
[25]	I. Contreras, J. F. Cordeau and G. Laporte, “Benders Decomposition for Large-Scale Uncapacitated Hub Location,” Cirrelt, Cirrelt-2010-26, 2010, pp. 1-43.
[26]	E. Rosenberg, “Hierarchical Topological Network Design,” IEEE/ACM Transactions on Networking, Vol. 13, No. 6, 2005, pp. 1402-1409. http://dx.doi.org/10.1109/TNET.2005.860100
[27]	I. Gódor and G. Magyar, “Cost-Optimal Topology Planning of Hierarchical Access Networks,” Computers & Operations Research, Vol. 32, No. 1, 2005, pp. 59-86. http://dx.doi.org/10.1016/S0305-0548(03)00202-8
[28]	T. Thomadsen and T. Stidsen, “The Generalized Fixed-Charge Network Design Problem,” Computers & Operations Research, Vol. 34, No. 4, 2007, pp. 997-1007. http://dx.doi.org/10.1016/j.cor.2005.05.021
[29]	J. F. Benders, “Partitioning Procedures for Solving Mixed Variables Programming Problems,” Numerrische Mathematik, Vol. 4, No. 1, 1962, pp. 238-252. http://dx.doi.org/10.1007/BF01386316
[30]	R. M. Freund, “Benders’ Decomposition Methods for Structured Optimization, including Stochastic Optimization,” Massachusetts Institute of Technology, 2004.
[31]	A. M. Costa, “A Survey on Benders Decomposition Applied to Fixed-Charge Network Design Problems,” Computers & Operations Research, Vol. 32, No. 6, 2005, pp. 1429-1450. http://dx.doi.org/10.1016/j.cor.2003.11.012
[32]	Y. Colombani and S. Heipcke, “Multiple Models and Parallel Solving with Mosel,” Xpress Team, FICO, Leam House, Leamington Spa CV32 5YN, 2008. http://www.fico.com/xpress
[33]	O. ?ak?r, “Benders Decomposition Applied to Multi-Commodity, Multi-Mode Distribution Planning,” Expert Systems with Applications, Vol. 36, No. 4, 2009, pp. 8212-8217. http://dx.doi.org/10.1016/j.eswa.2008.10.037?