The quadratic minimum spanning tree problem: lower bounds via extended formulations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929304197136384 |
|---|---|
| author | Sotirov, Renata Verchére, Zoe |
| author_facet | Sotirov, Renata Verchére, Zoe |
| contents | The quadratic minimum spanning tree problem (QMSTP) is the problem of finding a spanning tree of a graph such that the total interaction cost between pairs of edges in the tree is minimized. We first show that most of the bounding approaches for the QMSTP are closely related. Then, we exploit an extended formulation for the minimum spanning tree problem to derive a sequence of relaxations for the QMSTP with increasing complexity. The resulting relaxations differ from the relaxations in the literature. Namely, our relaxations have a polynomial number of constraints and can be efficiently solved by a cutting plane algorithm. Moreover our bounds outperform most of the bounds from the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_10647 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The quadratic minimum spanning tree problem: lower bounds via extended formulations Sotirov, Renata Verchére, Zoe Optimization and Control The quadratic minimum spanning tree problem (QMSTP) is the problem of finding a spanning tree of a graph such that the total interaction cost between pairs of edges in the tree is minimized. We first show that most of the bounding approaches for the QMSTP are closely related. Then, we exploit an extended formulation for the minimum spanning tree problem to derive a sequence of relaxations for the QMSTP with increasing complexity. The resulting relaxations differ from the relaxations in the literature. Namely, our relaxations have a polynomial number of constraints and can be efficiently solved by a cutting plane algorithm. Moreover our bounds outperform most of the bounds from the literature. |
| title | The quadratic minimum spanning tree problem: lower bounds via extended formulations |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2102.10647 |