Tensor-Network Formulation of the Traveling Salesman Problem and Variants
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916014221950976 |
|---|---|
| author | Ali, Alejandro Mata Delgado, Iñigo Perez de Leceta, Aitor Moreno Fdez. |
| author_facet | Ali, Alejandro Mata Delgado, Iñigo Perez de Leceta, Aitor Moreno Fdez. |
| contents | This work presents a tensor-network formulation of the Traveling Salesman Problem (TSP) and several of its variants. The approach represents candidate tours with tensor-network layers, weights them by Boltzmann factors, and enforces constraints through explicit counting filters. This formalism also yields an explicit tensor-network marginal formula whose zero-temperature, exact-arithmetic limit identifies an optimal feasible tour through a sequential marginal rule. At finite $τ$ and finite precision, the implemented extraction is a heuristic whose behavior depends on numerical contrast, calibration, and near-degeneracies. We adapt the construction to several generalizations of the TSP and apply it to the Job Reassignment Problem, as a representative industrial integration. The experiments are deliberately small and illustrative; they contextualize the method against exact and heuristic references but do not establish general computational superiority over specialized classical solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_14344 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tensor-Network Formulation of the Traveling Salesman Problem and Variants Ali, Alejandro Mata Delgado, Iñigo Perez de Leceta, Aitor Moreno Fdez. Quantum Physics Emerging Technologies 68Q12, 15A69, 90C27, 90B06 G.1.3; G.2.1 This work presents a tensor-network formulation of the Traveling Salesman Problem (TSP) and several of its variants. The approach represents candidate tours with tensor-network layers, weights them by Boltzmann factors, and enforces constraints through explicit counting filters. This formalism also yields an explicit tensor-network marginal formula whose zero-temperature, exact-arithmetic limit identifies an optimal feasible tour through a sequential marginal rule. At finite $τ$ and finite precision, the implemented extraction is a heuristic whose behavior depends on numerical contrast, calibration, and near-degeneracies. We adapt the construction to several generalizations of the TSP and apply it to the Job Reassignment Problem, as a representative industrial integration. The experiments are deliberately small and illustrative; they contextualize the method against exact and heuristic references but do not establish general computational superiority over specialized classical solvers. |
| title | Tensor-Network Formulation of the Traveling Salesman Problem and Variants |
| topic | Quantum Physics Emerging Technologies 68Q12, 15A69, 90C27, 90B06 G.1.3; G.2.1 |
| url | https://arxiv.org/abs/2311.14344 |