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

• DOI: 10.1007/s12532-016-0111-0
• Publication Date: 2016-09-24T07:01:11Z
• Authors: Matteo Fischetti; Markus Leitner; Ivana Ljubić; Martin Luipersbeck; Michele Monaci; Max Resch; Domenico Salvagnin; Markus Sinnl
• Keywords: Steiner tree problem; Solver; Theory of computation; Tree (set theory)

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