Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the problem of designing resilient communication networks with limited signal transmission distances, subject to uncertainty in both link lengths and node availability. The authors formulate the problem as a robust optimization model with budgeted uncertainty sets for regenerator installation costs and a novel dynamic budgeted uncertainty set for link lengths. They then develop scalable solution methods based on column-and-constraint generation, Benders decomposition, and iterative robust optimization, and further analyze the problem using a learning-based hide-and-seek game. The proposed methods outperform classical robust models and deterministic worst-case formulations.
Designing resilient networks under uncertainty is now more tractable thanks to new scalable robust optimization methods and a hide-and-seek game formulation.
We study the design of resilient and reliable communication networks in which a signal can be transferred only up to a limited distance before its quality falls below an acceptable threshold. When excessive signal degradation occurs, regeneration is required through regenerators installed at selected network nodes. In this work, both network links and nodes are subject to uncertainty. The installation costs of regenerators are modeled using a budgeted uncertainty set. In addition, link lengths follow a dynamic budgeted uncertainty set introduced in this paper, where deviations may vary over time. Robust optimization seeks solutions whose performance is guaranteed under all scenarios represented by the underlying uncertainty set. Accordingly, the objective is to identify a minimum-cost subset of nodes for regenerator deployment that ensures full network connectivity, even under the worst possible realizations of uncertainty. To solve the problem, we first formulate it within a robust optimization framework, and then develop scalable solution methods based on column-and-constraint generation, Benders decomposition, and iterative robust optimization. In addition, we formulate a learning-based hide-and-seek game to further analyze the problem structure. The proposed approaches are evaluated against classical static budgeted robust models and deterministic worst-case formulations. Both theoretical analysis and computational results demonstrate the effectiveness and advantages of our methodology.