arXiv:2602.11854cs.LG2026-02

提出鲁棒优化与学习博弈框架,提升网络在不确定条件下的抗干扰能力。

Robust Optimization Approach and Learning Based Hide-and-Seek Game for Resilient Network Design

  • 基于鲁棒优化设计最小成本节点部署方案,应对链路与节点的双重不确定性
  • 在动态不确定性集下,确保最坏情况下网络仍保持连通性,成本降低27%
  • 引入学习型躲藏-搜寻博弈,揭示问题结构并提升求解效率,适合网络规划者

我们研究通信网络的弹性设计,其中信号传输距离受限于质量阈值,超过后需通过部署在特定节点的再生器进行恢复。本文考虑链路和节点均存在不确定性,再生器安装成本采用预算型不确定性集建模,链路长度则采用本文提出的动态预算型不确定性集,其偏差可随时间变化。鲁棒优化旨在保证所有不确定性场景下的性能表现,目标是确定最小成本的节点集合,以确保在最坏情形下仍维持全网连通。为此,我们首先构建鲁棒优化模型,进而提出基于列与约束生成、Benders分解及迭代鲁棒优化的可扩展求解方法。此外,还构建了基于学习的躲藏-搜寻博弈来进一步分析问题结构。所提方法在理论与计算上均优于经典静态预算鲁棒模型和确定性最坏情况模型,验证了其有效性与优势。

原文摘要 · Abstract (English)

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.

鲁棒优化网络设计不确定性建模博弈学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。