Fixed Topology Minimum-Length Trees with Neighborhoods
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913492856995840 |
|---|---|
| author | Blanco, Víctor González, Gabriel Puerto, Justo |
| author_facet | Blanco, Víctor González, Gabriel Puerto, Justo |
| contents | In this paper, we introduce the Fixed Topology Minimum-Length Tree with Neighborhood Problem, which aims to embed a rooted tree-shaped graph into a $d$-dimensional metric space while minimizing its total length provided that the nodes must be embedded to some restricted areas. This problem has significant applications in efficiently routing cables or pipelines in engineering designs. We propose novel mathematical optimization-based approaches to solve different versions of the problem based on the domain for the embedding. In cases where the embedding maps to a continuous space, we provide several Mixed Integer Nonlinear Optimization formulations. If the embedding is to a network, we derive a mixed integer linear programming formulation as well as a dimensionality reduction methodology that allows for solving larger problems in less CPU time. A data-driven methodology is also proposed to construct a proper network based on the instance of the problem. We report the results of a battery of computational experiments that validate our proposal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04152 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fixed Topology Minimum-Length Trees with Neighborhoods Blanco, Víctor González, Gabriel Puerto, Justo Optimization and Control 90C27, 05C05, 90C11, 90C30 In this paper, we introduce the Fixed Topology Minimum-Length Tree with Neighborhood Problem, which aims to embed a rooted tree-shaped graph into a $d$-dimensional metric space while minimizing its total length provided that the nodes must be embedded to some restricted areas. This problem has significant applications in efficiently routing cables or pipelines in engineering designs. We propose novel mathematical optimization-based approaches to solve different versions of the problem based on the domain for the embedding. In cases where the embedding maps to a continuous space, we provide several Mixed Integer Nonlinear Optimization formulations. If the embedding is to a network, we derive a mixed integer linear programming formulation as well as a dimensionality reduction methodology that allows for solving larger problems in less CPU time. A data-driven methodology is also proposed to construct a proper network based on the instance of the problem. We report the results of a battery of computational experiments that validate our proposal. |
| title | Fixed Topology Minimum-Length Trees with Neighborhoods |
| topic | Optimization and Control 90C27, 05C05, 90C11, 90C30 |
| url | https://arxiv.org/abs/2409.04152 |