SCIP-Jack – A solver for STP and variants with parallelization extensions

Please always quote using this URN: urn:nbn:de:0297-zib-60170
  • The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt, Yuji Shinano
Document Type:ZIB-Report
Tag:maximum-weight connected subgraph; prize-collecting Steiner tree
SCIP-Jack; Steiner tree problem; Steiner tree variants
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:D. Software
Date of first Publication:2016/08/16
Series (Serial Number):ZIB-Report (16-41)
ISSN:1438-0064
Published in:to appear in Mathematical Programming Computation
DOI:http://dx.doi.org/10.1007/s12532-016-0114-x

$Rev: 13581 $