Optimization based algorithms for finding minimal cost ring covers in survivable networks

Designing low cost SONET networks composed of self-healing rings is an impo rtant problem facing the providers of broadband services. This manuscript d emonstrates how optimization technology coupled with the highly efficient C PLEX software system can be used to help solve this important problem. For the first time, provable optimal designs are presented for several small ne tworks which appear in the literature. In an empirical analysis, we demonst rate how this same methodology can be used to find good (but not provably o ptimal) designs for large test cases.