Metraipolis › archive › dc_56d79df498ef

Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design — arXiv:2609.39269

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.39269
License (as archived): CC0-1.0
Archived: 2026-10-07T14:11:22.797Z
SHA-256 of the archived text: c806783af4990011d1a1267afae71004473f90c51cd15fd2598c6d131f326997
Stable URL of this page: https://metraipolis.com/documento/dc_56d79df498ef

How to cite

Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design — arXiv:2609.39269 — arXiv (en), https://arxiv.org/abs/2609.39269 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_56d79df498ef (Metraipolis archive dc_56d79df498ef, sha256 c806783af4990011d1a1267afae71004473f90c51cd15fd2598c6d131f326997)

BibTeX

@misc{dc56d79df498ef,
  title = {Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design — arXiv:2609.39269},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39269},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_56d79df498ef; sha256 c806783af4990011d1a1267afae71004473f90c51cd15fd2598c6d131f326997},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39269. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.39269 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:03:18.261Z dalla pagina https://arxiv.org/catchup/math.OC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).