Paperlane

no. 3 · Tuesday 27 October 2026

Robust Network Enhancement: Formulations and Approximations

Zolykha Rezaei and Ningji Wei

math.OC · 22 pp

Abstract

We study robust network enhancement problems that improve network performance through component upgrades, where both network utilities and enhancement costs are uncertain. We consider two formulations: a lower-bound problem that improves the minimum utility across feasible network structures and an upper-bound problem that improves the maximum utility. For the lower-bound problem, we develop an exact cut-generation reformulation and identify the robust separation subproblem as a key computational bottleneck. We characterize conditions under which fractional extreme points arise in the linearized robust formulation and demonstrate that such points can be optimal. For the upper-bound problem, we derive two exact reformulations and compare the strength of their linear relaxations. To improve computational tractability, we introduce a box approximation of the utility uncertainty set that preserves solution robustness and provides explicit performance guarantees for both lower- and upper-bound problems. Computational experiments on spanning tree instances show that the proposed approximation improves computational efficiency for both problems while maintaining solution quality close to that of the exact formulations.

comments
22 pages, 2 tables
fields
Optimization and Control
pdf ↗ page arXiv:2610.34811 ↗