Thinning out Steiner trees: a node based model for uniform edge costs

Matteo Fischetti, M. Leitner, Ivana Ljubic, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin, Markus Sinnl

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The Steiner tree problem is a challenging NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut codes. A typical strategy to attack these instances is to enrich the polyhedral description of the problem, and/or to implement more and more sophisticated separation procedures and branching strategies. In this paper we investigate the opposite viewpoint, and try to make the solution method as simple as possible while working on the modeling side. Our working hypothesis is that the extreme hardness of some classes of instances mainly comes from over-modeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. In our computational study, we first show that this new model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. Moreover, we report improved solutions for several SteinLib instances, including the (in)famous hypercube ones. We also demonstrate how to build a unified solver on top of the new node-based model and the previous state-of-the-art model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually. The presented solver is the winner of the DIMACS Challenge on Steiner trees in most of the considered categories.
Original languageEnglish
Pages (from-to)203-229
Number of pages27
JournalMathematical Programming Computation
Volume9
Issue number2
DOIs
Publication statusPublished - 2017

Funding

The research of the Padova’s group was supported by the University of Padova (Progetto di Ateneo “Exploiting randomness in Mixed Integer Linear Programming”), and by MiUR, Italy (PRIN project “Mixed-Integer Nonlinear Optimization: Approaches and Applications”). The research of the Vienna’s group was supported by the Austrian Research Fund (FWF, Projects P 26755-N19 and I 892-N23). The work of M. Sinnl was supported by an STSM Grant from COST Action TD1207; the authors would like to acknowledge networking support by the same COST action. M. Luipersbeck acknowledges the support of the University of Vienna through the uni:docs fellowship programme.

FundersFunder number
European Cooperation in Science and TechnologyTD1207
Austrian Science FundP 26755-N19, I 892-N23
Universität Wien
Ministero dell’Istruzione, dell’Università e della Ricerca
Università degli Studi di Padova

    Keywords

    • Exact computation
    • Mixed integer programming

    Fingerprint

    Dive into the research topics of 'Thinning out Steiner trees: a node based model for uniform edge costs'. Together they form a unique fingerprint.

    Cite this