A Robust Optimization Approach for Regenerator Placement in Fault-Tolerant Networks Under Discrete Cost Uncertainty

Abstract

We focus on robust, survivable communication networks, where network links and nodes are affected by an uncertainty set. In this sense, any network links might fail. Besides, a signal can only travel a maximum distance before its quality falls below a certain threshold, necessitating its regeneration by regenerators installed at network nodes. In addition, the price of installing and maintaining regenerators belongs to a discrete uncertainty set. Robust optimization seeks a solution with guaranteed performance against all scenarios modeled in an uncertainty set. Thus, the problem is to find a subset of nodes with minimum cost for the placement of the regenerator, ensuring that all nodes can communicate even if a subset of network links fails. To solve the problem optimally, we propose two solution approaches, including one flow-based and one cut-based integer programming formulation, as well as their iterative exact method. Our theoretical and experimental results show the effectiveness of our methods.