Robust Network Enhancement: Formulations and Approximations
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.
Related
- Optimality and Exact Moment-SDP Formulations for Robust Two-Stage Convex Polynomial Multiobjective Optimization
- Robust preconditioners for finite element approximations of control-state constrained optimal control problems governed by elliptic equations
- Locally computable error estimators for conforming approximations of interface problems cannot be robust
- A family of spectral conjugate gradient algorithms derived by least-squares approximations based on a modified quasi--Newton update with application to a revised robust binary classification model
- Stable time-stepping via residual minimization: finite-element and neural-network approximations for transient parabolic problems
BibTeX
@misc{rezaei2026robust,
title = {{Robust Network Enhancement: Formulations and Approximations}},
author = {Zolykha Rezaei and Ningji Wei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34811},
eprint = {2610.34811},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34811},
}
RIS
TY - UNPB
TI - Robust Network Enhancement: Formulations and Approximations
AU - Zolykha Rezaei
AU - Ningji Wei
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34811
UR - https://arxiv.org/abs/2610.34811
AB - 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.
ER -