Optimization algorithms for survivable network design problems

We address difficult optimization problems in designing survivable fiber-optic telecommunications networks used for voice communication and such vital commercial transactions as order processing and inventory control. An important consideration in their design is survivability: their ability to continue to provide communication between sites in the event that links (spans of fiber-optic cable between two sites on the network) are cut or otherwise fail.;To be economically viable, fiber-optic networks are usually built so that small numbers of routes, and consequently individual cables, carry high volumes of traffic. The loss of even one link can result in a severe service disruption. Specifically, we study problems in the design of networks employing the Synchronous Optical NETwork (SONET) technology. SONET systems typically enhance survivability by using self-healing rings (SHRS) which employ redundant, or spare, links to provide automatic rerouting of traffic in the event of fiber cable failures.;We consider the question of providing redundancy sufficient to ensure a high degree of survivability while minimizing the cost of the extra links in networks of multiple SHRs. We formulate the Bounded Cycle Cover Problem (BCCP). We show that BCCP is MP-hard and present heuristic algorithms that obtain near-optimal solutions at a modest cost of computing resources (e.g., CPU time).;To optimize a design used by a major European telecommunications provider for building its customers' networks, we formulate the SONET Ring Assignment Problem (SRAP). SRAP seeks a partition of a graph's nodes into a minimum number of sets. The total weight of the edges incident to any set, and also the total weight of all edges incident to two different sets, may not exceed a given constant. We present exact solution techniques and fast, easily-implemented heuristics for solving this NP -hard problem. We show that 1 the heuristics never use more than twice the minimum number of sets.;We consider the SONET Edge Partition Problem which is to cover the edges of a graph using subgraphs containing at most k edges while minimizing the total number of vertices in the subgraphs. We present linear-time O ( k )-approximation algorithms for NP -hard cases where k ≥ 3.;This disseration's central contributions are (i) the formulation of optimization models for SONET design problems, (ii) development of practical algorithms to solve these problems, and (iii) theoretical and empirical analyses of the algorithms' performance.