A Spatial Benders Algorithm for Delay Constrained Routing
Abstract
We study the Delay Constrained Routing (DCR) problem arising in IP computer networks to support high bandwidth applications. The goal is to route IP packets, from source to destination, subject to quality of service constraints -- in particular, bounding the worst case delay -- while minimizing the total allocated bandwidth in the network. DCR can be formulated as a Mixed-Integer Second-Order Cone Program, and solved using standard solvers; while generally efficient, this hinges on off-the-shelf tools and does not scale to large instances. We devise a solver-free bespoke approach that uses nested Benders-Lagrange, namely, a double decomposition approach that exploits the special structure of the problem. In particular, we use a nonconvex nonlinear formulation of the problem, that results in a nonconvex Benders value function whose optimization we tackle with a bespoke Spatial Branch-and-Bound approach using custom piecewise-convex cuts. We show that our approach provides very tight upper and lower bounds in competitive running times w.r.t. previous state-of-the-art approaches.
Related
- A Quantum-Classical Benders Decomposition for Cargo Routing with Time Windows
- Chance-Constrained Personalized LLM Routing with Online Preference Learning
- BERS: Locally Optimal Continuous Algorithm for Maritime Weather Routing with Just-in-Time Arrival
- An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
- On the Delay-Constrained Maximum Concurrent Flow Problem
BibTeX
@misc{frangioni2026spatial,
title = {{A Spatial Benders Algorithm for Delay Constrained Routing}},
author = {Antonio Frangioni and Laura Galli and Luca Mencarelli and Enrico Sorbera},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37528},
eprint = {2609.37528},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37528},
}
RIS
TY - UNPB
TI - A Spatial Benders Algorithm for Delay Constrained Routing
AU - Antonio Frangioni
AU - Laura Galli
AU - Luca Mencarelli
AU - Enrico Sorbera
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37528
UR - https://arxiv.org/abs/2609.37528
AB - We study the Delay Constrained Routing (DCR) problem arising in IP computer networks to support high bandwidth applications. The goal is to route IP packets, from source to destination, subject to quality of service constraints -- in particular, bounding the worst case delay -- while minimizing the total allocated bandwidth in the network. DCR can be formulated as a Mixed-Integer Second-Order Cone Program, and solved using standard solvers; while generally efficient, this hinges on off-the-shelf tools and does not scale to large instances. We devise a solver-free bespoke approach that uses nested Benders-Lagrange, namely, a double decomposition approach that exploits the special structure of the problem. In particular, we use a nonconvex nonlinear formulation of the problem, that results in a nonconvex Benders value function whose optimization we tackle with a bespoke Spatial Branch-and-Bound approach using custom piecewise-convex cuts. We show that our approach provides very tight upper and lower bounds in competitive running times w.r.t. previous state-of-the-art approaches.
ER -