Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner 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_ | 1866912254006394880 |
|---|---|
| author | Bernardelli, Ambrogio Maria Vercesi, Eleonora Gualandi, Stefano Mastrolilli, Monaldo Gambardella, Luca Maria |
| author_facet | Bernardelli, Ambrogio Maria Vercesi, Eleonora Gualandi, Stefano Mastrolilli, Monaldo Gambardella, Luca Maria |
| contents | In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (BCR) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the BCR formulation on metric instances. A key contribution of our work is extending the Gap problem, previously explored in the context of the Traveling Salesman problems, to the metric Steiner Tree problem. To tackle the Gap problem for Steiner Tree instances, we first establish several structural properties of the CM formulation. We then classify the isomorphism classes of the vertices within the CM polytope, revealing a correspondence between the vertices of the BCR and CM polytopes. Computationally, we exploit these structural properties to design two complementary heuristics for finding nontrivial small metric Steiner instances with a large integrality gap. We present several vertices for graphs with a number of nodes <=10, which realize the best-known lower bounds on the integrality gap for the CM and the BCR formulations. We conclude the paper by presenting two new conjectures on the integrality gap of the BCR and CM formulations for small graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem Bernardelli, Ambrogio Maria Vercesi, Eleonora Gualandi, Stefano Mastrolilli, Monaldo Gambardella, Luca Maria Optimization and Control Discrete Mathematics In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (BCR) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the BCR formulation on metric instances. A key contribution of our work is extending the Gap problem, previously explored in the context of the Traveling Salesman problems, to the metric Steiner Tree problem. To tackle the Gap problem for Steiner Tree instances, we first establish several structural properties of the CM formulation. We then classify the isomorphism classes of the vertices within the CM polytope, revealing a correspondence between the vertices of the BCR and CM polytopes. Computationally, we exploit these structural properties to design two complementary heuristics for finding nontrivial small metric Steiner instances with a large integrality gap. We present several vertices for graphs with a number of nodes <=10, which realize the best-known lower bounds on the integrality gap for the CM and the BCR formulations. We conclude the paper by presenting two new conjectures on the integrality gap of the BCR and CM formulations for small graphs. |
| title | Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2405.13773 |