TITLE:
Reliable Network Design Problem under Node Failure with Benders Decomposition
AUTHORS:
Tie Liu, Wenguo Yang, Jun Huang
KEYWORDS:
Mixed-Integer Programming; Benders Decomposition; Network Design; Node Failure
JOURNAL NAME:
Applied Mathematics,
Vol.5 No.2,
January
17,
2014
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.