Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply netwo rk with point-to-point traffic demands, specific survivability requirements , a set of available capacity ranges and their corresponding discrete costs for each are, find minimum cost capacity expansions such that these demand s can be met even if a network component fails. Solving this problem consis ts of selecting the links and their capacity, as well as the routings for e ach demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulatio n is presented. An effective solution procedure based on Lagrangean relaxat ion is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.