Design of Survivable Optical Networks by Mathematical Optimization

The cost-e?cient design of survivable optical telecommunication networks is the topic of this thesis. In cooperation with network operators, we have developed suitable concepts and mathematical optimization methods to solve this comprehensive planningtask in practice. Optical technology is more and more employed in modern telecommunication net-works.Digital information is therebytransmittedas short light pulses through glass ?bers. Moreover, the optical medium allows for simultaneous transmissions on a single ?ber by use of di?erent wavelengths. Recent optical switches enable a direct forwarding of optical channels in the network nodes without the previously required signalretransformation to electronics. Their integration creates ongoingopticalconnections, which are called lightpaths. We study the problem of ?nding cost-e?cient con?gurations of optical networks which meet speci?ed communication requirements. A con?guration comprises the determination of all lightpaths to establish as well as the detailed allocation of all required devices and systems. We use a ?exible modeling framework for a realistic representation of the networks and their composition.For di?erentnetworkarchitectures, we formulate integer linear programs which model the design task in detail. Moreover, network survivability is an important issue due to the immense bandwidths o?ered by optical technology. Operators therefore request for designs which perpetuate protected connections and guarantee for a de?ned minimum throughput in case of malfunctions. In order to achieve an e?ective realization of scalable protection, we present a novel survivability concept tailored to optical networks and integrate several variants into the models. Our solution approach is based on a suitable model decomposition into two subtasks which separates two individually hard subproblems and enables this way to compute cost-e?cient designs with approved quality guarantee. The ?rst subtask consists of routing the connections with corresponding dimensioning of capacities and constitutes a common core task in the area of network planning. Sophisticated methods for such problems have already been developed and are deployed by appropriate integration. The second subtask is characteristic for optical networks and seeks for a con?ict-free assignment of available wavelengths to the lightpaths using a minimum number of involved wavelength converters. For this coloring-like task, we derive particular models and study methods to estimate the number of unavoidable conversions. As constructive approach, we develop heuristics and an exact branch-and-price algorithm. Finally, we carry out an extensive computational study on realistic data, provided by our industrial partners. As twofold purpose, we demonstrate the potential of our approach for computing good solutions with quality guarantee, and we exemplify its ?exibility for application to network design and analysis.