Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements.
Appeared in: Operations Research 43 (1995) 1012-1024
| SC 92-24 | Martin Grötschel, C. L. Monma, Mechthild Stoer
Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements. Appeared in: Operations Research 43 (1995) 1012-1024 | |
Abstract: We consider the important practical and
theoretical problem of designing a low-cost communications
network which can survive failures of certain network
components. Our initial interest in this area was motivated
by the need to design certain ``two-connected" survivable
topologies for fiber optic communication networks of
interest to the regional telephone companies. In this paper,
we describe some polyhedral results for network design
problems with higher connectivity requirements. We also
report on some preliminary computational results for a
cutting plane algorithm for various real-world and random
problems with high connectivity requirements which shows
promise for providing good solutions to these difficult
problems.