Shared Protection Network Design through
 Lagrangian Relaxation

by

Pietro Belotti
Politecnico di Milano 

As optical networks are more and more used to implement medium- and
large-scale communication backbones, network planners have to cope with
their high installation and maintenance costs. We focus on Shared
Protection (SP), a feature we believe to be very effective in reducing the
cost of backup resources in survivable networks. Integer Linear models of
network design with SP show to be hardly tractable from a computational
viewpoint, hence we study a Lagrangian Relaxation of the problem and solve
it with a bundle method. Our approach shows to be much more efficient than
an MIP solver on a set of real-world network instances.