Reliable Network Design Problem under Node Failure with Benders Decomposition

HTML  XML Download Download as PDF (Size: 837KB)  PP. 241-255  
DOI: 10.4236/am.2014.52026    3,467 Downloads   5,281 Views  Citations

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.

Share and Cite:

T. Liu, W. Yang and J. Huang, "Reliable Network Design Problem under Node Failure with Benders Decomposition," Applied Mathematics, Vol. 5 No. 2, 2014, pp. 241-255. doi: 10.4236/am.2014.52026.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.