Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917900473860096 |
|---|---|
| author | Martin, Sébastien Bauguion, Pierre Magnouche, Youcef Leguay, Jérémie |
| author_facet | Martin, Sébastien Bauguion, Pierre Magnouche, Youcef Leguay, Jérémie |
| contents | In real-life applications, most optimization problems are variants of well-known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist, or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so-called atomic algorithms to solve an optimization problem including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig-Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch-and-Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource-constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation Martin, Sébastien Bauguion, Pierre Magnouche, Youcef Leguay, Jérémie Discrete Mathematics In real-life applications, most optimization problems are variants of well-known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist, or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so-called atomic algorithms to solve an optimization problem including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig-Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch-and-Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource-constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms. |
| title | Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2501.13463 |