SCIP-Jack — a solver for STP and variants with parallelization extensions. 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.

References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Ritt, Marcus; Pereira, Jordi: Heuristic and exact algorithms for minimum-weight non-spanning arborescences (2020)
  2. Rehfeldt, Daniel; Koch, Thorsten: Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem (2019)
  3. Rehfeldt, Daniel; Koch, Thorsten; Maher, Stephen J.: Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem (2019)
  4. Shinano, Yuji; Rehfeldt, Daniel; Koch, Thorsten: Building optimal Steiner trees on supercomputers by using up to 43,000 cores (2019)
  5. Di Puglia Pugliese, Luigi; Gaudioso, Manlio; Guerriero, Francesca; Miglionico, Giovanna: A Lagrangean-based decomposition approach for the link constrained Steiner tree problem (2018)
  6. Leitner, Markus; Ljubić, Ivana; Luipersbeck, Martin; Sinnl, Markus: Decomposition methods for the two-stage stochastic Steiner tree problem (2018)
  7. Pajor, Thomas; Uchoa, Eduardo; Werneck, Renato F.: A robust and scalable algorithm for the Steiner problem in graphs (2018)
  8. Rehfeldt, Daniel; Koch, Thorsten: Transformations for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to sap (2018)
  9. Shinano, Yuji: The ubiquity generator framework: 7 years of progress in parallelizing branch-and-bound (2018)
  10. Fu, Zhang-Hua; Hao, Jin-Kao: Swap-vertex based neighborhood for Steiner tree problems (2017)
  11. Gamrath, Gerald; Koch, Thorsten; Maher, Stephen J.; Rehfeldt, Daniel; Shinano, Yuji: SCIP-Jack -- a solver for STP and variants with parallelization extensions (2017)
  12. Liers, Frauke; Martin, Alexander; Pape, Susanne: Binary Steiner trees: structural results and an exact solution approach (2016)