Lexicographic Minimax Load Balancing for T-Adaptive Segment Routing
Abstract
We introduce the T-Adaptive Segment Routing, a multi-period optimization problem that emerges in the traffic engineering of core IP/MPLS networks when scheduled maintenance operations are involved. The problem seeks a sequence of Segment Routing (SR) configurations that can adapt to a multi-period scheduled maintenance, while allowing limited number of path reconfigurations between successive time steps. Instead of only minimizing the classical Maximum Link Utilization (MLU) criteria, we propose a more refined lexicographic objective that minimizes the sorted vector of link loads in its entirety, thereby enabling a more efficient resource utilization across all links. To tackle this problem, we develop three exact formulations for solving the resulting lexicographic optimization problem. Among these, the Stela and Carla formulations provide the most favorable computational basis for trajectory-based optimization. We thus develop a trajectory column-generation scheme for these formulations, using pricing oracles that vary from heuristic to exact. Exact pricing gives an exact solution of the LP relaxation of the trajectory master, but it does not itself give a certificate of integer optimality: solving the integer master over the columns generated at the root node only certifies optimality within the generated column pool. To overcome this gap, we incorporate trajectory column generation into a Branch-and-Price framework. The branching rule operates on aggregate variables representing segment usage, which correspond to the original compact routing variables. Thus, Branch-and-Price guarantees global integer optimality for every Stela and Carla rank, and when all ranks are solved to exactness, it guarantees lexicographic optimality of the final solution.
Related
- On the T-Adaptive Segment Routing Problem
- Expected Minimax Regret Rates for Adaptive LQG Control on Fixed Parameter Sets
- Minimax and adaptive inference for branching ratios under long memory
- Minimax and Adaptive Transfer Learning for Sparse Canonical Correlation Analysis
- Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control
BibTeX
@misc{bouaachra2026lexicographic,
title = {{Lexicographic Minimax Load Balancing for T-Adaptive Segment Routing}},
author = {Kaoutar Bouaachra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36338},
eprint = {2609.36338},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36338},
}
RIS
TY - UNPB
TI - Lexicographic Minimax Load Balancing for T-Adaptive Segment Routing
AU - Kaoutar Bouaachra
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36338
UR - https://arxiv.org/abs/2609.36338
AB - We introduce the T-Adaptive Segment Routing, a multi-period optimization problem that emerges in the traffic engineering of core IP/MPLS networks when scheduled maintenance operations are involved. The problem seeks a sequence of Segment Routing (SR) configurations that can adapt to a multi-period scheduled maintenance, while allowing limited number of path reconfigurations between successive time steps. Instead of only minimizing the classical Maximum Link Utilization (MLU) criteria, we propose a more refined lexicographic objective that minimizes the sorted vector of link loads in its entirety, thereby enabling a more efficient resource utilization across all links. To tackle this problem, we develop three exact formulations for solving the resulting lexicographic optimization problem. Among these, the Stela and Carla formulations provide the most favorable computational basis for trajectory-based optimization. We thus develop a trajectory column-generation scheme for these formulations, using pricing oracles that vary from heuristic to exact. Exact pricing gives an exact solution of the LP relaxation of the trajectory master, but it does not itself give a certificate of integer optimality: solving the integer master over the columns generated at the root node only certifies optimality within the generated column pool. To overcome this gap, we incorporate trajectory column generation into a Branch-and-Price framework. The branching rule operates on aggregate variables representing segment usage, which correspond to the original compact routing variables. Thus, Branch-and-Price guarantees global integer optimality for every Stela and Carla rank, and when all ranks are solved to exactness, it guarantees lexicographic optimality of the final solution.
ER -