Implications, conflicts, and reductions for Steiner trees

dc.contributor.authorRehfeldt, Daniel
dc.contributor.authorKoch, Thorsten
dc.date.accessioned2022-10-04T09:38:43Z
dc.date.available2022-10-04T09:38:43Z
dc.date.issued2021-12-30
dc.description.abstractThe Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot match the state of the art on the vast majority of benchmark instances. The following article seeks to advance exact SPG solution once again. The article is based on a combination of three concepts: Implications, conflicts, and reductions. As a result, various new SPG techniques are conceived. Notably, several of the resulting techniques are (provably) stronger than well-known methods from the literature that are used in exact SPG algorithms. Finally, by integrating the new methods into a branch-and-cut framework, we obtain an exact SPG solver that is not only competitive with, but even outperforms the current state of the art on an extensive collection of benchmark sets. Furthermore, we can solve several instances for the first time to optimality.en
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2021en
dc.description.sponsorshipBMBF, 05M14ZAM, Forschungscampus Modal - Mathematical Optimization and Data Analysis Laboratories. Antrag auf die erste Hauptphase (Implementierung) des Forschungscampus Modalen
dc.identifier.eissn1436-4646
dc.identifier.issn0025-5610
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/17035
dc.identifier.urihttps://doi.org/10.14279/depositonce-15814
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc510 Mathematikde
dc.subject.otherSteiner tree problemen
dc.subject.otheroptimal solutionen
dc.subject.otherreduction techniquesen
dc.titleImplications, conflicts, and reductions for Steiner treesen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.doi10.1007/s10107-021-01757-5en
dcterms.bibliographicCitation.journaltitleMathematical Programmingen
dcterms.bibliographicCitation.originalpublishernameSpringer Natureen
dcterms.bibliographicCitation.originalpublisherplaceHeidelbergen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Software und Algorithmen für die diskrete Optimierungde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.groupFG Software und Algorithmen für die diskrete Optimierungde
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Rehfeldt_Koch_Implications_2021.pdf
Size:
820.95 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.86 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections