Designing Capacitated Subnetworks for Shortest Path Routing

Markus Chimani, Max Ilsen · 2026

Read Designing Capacitated Subnetworks for Shortest Path Routing by Markus Chimani, Max Ilsen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06319.txt.

Description

Markus Chimani and Max Ilsen tackle green traffic engineering for computer networks under shortest path routing. To save energy, operators want to switch off network links in quiet hours while still routing every demand that arrives. That means solving a design problem, which links to deactivate, and a routing problem together. For the common shortest path paradigm, no method handled the combined problem as a whole until now.

Their exact algorithm rests on a new integer linear program that models shortest paths changing dynamically as links drop. A special purpose column generation method solves it, strengthened by extra provably valid constraints. With true optima available for small practical cases, they benchmark the simpler heuristics used in practice. One simple fix the routing first method lands surprisingly close to optimal.

Catalog record

CREATORMarkus Chimani, Max Ilsen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06319

Browse the full library · About the Tower of Babel