SCIP-Jack—a solver for STP and variants with parallelization extensions: An update

accepted for publication on 2017-11-01
  • The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. 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. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Daniel Rehfeldt, Thorsten Koch
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2017
Year of first publication:2017
Preprint:urn:nbn:de:0297-zib-66416