Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design
Abstract
Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the relaxation solution that make it infeasible for the original problem and then apply fixes to the relaxation to prevent them from recurring. We study the optimal refinement problem of selecting from a set of fixes a subset that fixes all conflicts and yields a relaxation of minimum size, with the aim of making it easier to solve. We demonstrate that while the number of conflicts may be exponential in the instance parameters, we can represent them more compactly, using only pseudo-polynomial space and time. Based on our more compact representation, we develop exact methods for solving the refinement problem. The best method allows us to find small relaxations in negligible amounts of time, more than 100 times faster than a natural integer programming formulation for some instance classes. Using this refinement approach in a DDD algorithm for the CTSNDP, we observe reductions in model sizes and running times of about 10 to 20 % compared to existing approaches.
Related
- Adaptive Grid Refinement for Optimal Feedback Control
- Mutual Information Optimal Density Control of Linear Systems and Generalized Schrödinger Bridges with Reference Refinement
- Optimal Transport for Continuous-Time Mean-Variance Portfolio Selection
- MARCEDES: Score-based causal discovery under non-Gaussianity with continuous optimization
- Stability, discretization, and optimality of continuous-time causal optimal transport
BibTeX
@misc{helber2026optimal,
title = {{Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design}},
author = {Alexander Helber and Oliver Bachtler and Tom Wüllner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39269},
eprint = {2609.39269},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39269},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design
AU - Alexander Helber
AU - Oliver Bachtler
AU - Tom Wüllner
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39269
UR - https://arxiv.org/abs/2609.39269
AB - Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the relaxation solution that make it infeasible for the original problem and then apply fixes to the relaxation to prevent them from recurring. We study the optimal refinement problem of selecting from a set of fixes a subset that fixes all conflicts and yields a relaxation of minimum size, with the aim of making it easier to solve. We demonstrate that while the number of conflicts may be exponential in the instance parameters, we can represent them more compactly, using only pseudo-polynomial space and time. Based on our more compact representation, we develop exact methods for solving the refinement problem. The best method allows us to find small relaxations in negligible amounts of time, more than 100 times faster than a natural integer programming formulation for some instance classes. Using this refinement approach in a DDD algorithm for the CTSNDP, we observe reductions in model sizes and running times of about 10 to 20 % compared to existing approaches.
ER -