Exact Minimum Weight Spanners via Column Generation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910504419590144 |
|---|---|
| author | Bökler, Fritz Chimani, Markus Jasper, Henning Wagner, Mirko H. |
| author_facet | Bökler, Fritz Chimani, Markus Jasper, Henning Wagner, Mirko H. |
| contents | Given a weighted graph $G$, a minimum weight $α$-spanner is a least-weight subgraph $H\subseteq G$ that preserves minimum distances between all node pairs up to a factor of $α$. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [20]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [48] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [2], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable.
In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16000 nodes within 13 minutes. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19164 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact Minimum Weight Spanners via Column Generation Bökler, Fritz Chimani, Markus Jasper, Henning Wagner, Mirko H. Data Structures and Algorithms Discrete Mathematics Combinatorics 68R10 (Primary) 05C85, 90C11 (Secondary) F.2.2; G.2.1; G.2.2 Given a weighted graph $G$, a minimum weight $α$-spanner is a least-weight subgraph $H\subseteq G$ that preserves minimum distances between all node pairs up to a factor of $α$. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [20]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [48] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [2], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16000 nodes within 13 minutes. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time. |
| title | Exact Minimum Weight Spanners via Column Generation |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 68R10 (Primary) 05C85, 90C11 (Secondary) F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2406.19164 |