Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908657990500352 |
|---|---|
| author | de Meijer, Frank Siebenhofer, Melanie Sotirov, Renata Wiegele, Angelika |
| author_facet | de Meijer, Frank Siebenhofer, Melanie Sotirov, Renata Wiegele, Angelika |
| contents | In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation for the QMSTP and investigate classes of valid inequalities to strengthen the relaxation using the Chvátal-Gomory procedure for mixed-integer conic programming. Solving the resulting relaxations is out of reach for off-the-shelf software. We therefore develop and implement a version of the Peaceman-Rachford splitting method that allows to compute the new bounds for graphs from the literature. The computational results demonstrate that our bounds significantly improve over existing bounds from the literature in both quality and computation time, in particular for graphs with more than 30 vertices. This work is further evidence that semidefinite programming is a valuable tool to obtain high-quality bounds for problems in combinatorial optimization, in particular for those that can be modelled as a quadratic problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04997 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem de Meijer, Frank Siebenhofer, Melanie Sotirov, Renata Wiegele, Angelika Optimization and Control In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation for the QMSTP and investigate classes of valid inequalities to strengthen the relaxation using the Chvátal-Gomory procedure for mixed-integer conic programming. Solving the resulting relaxations is out of reach for off-the-shelf software. We therefore develop and implement a version of the Peaceman-Rachford splitting method that allows to compute the new bounds for graphs from the literature. The computational results demonstrate that our bounds significantly improve over existing bounds from the literature in both quality and computation time, in particular for graphs with more than 30 vertices. This work is further evidence that semidefinite programming is a valuable tool to obtain high-quality bounds for problems in combinatorial optimization, in particular for those that can be modelled as a quadratic problem. |
| title | Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.04997 |