SCIP-Jack - A massively parallel STP solver

Please always quote using this URN: urn:nbn:de:0297-zib-52293
  • In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Gerald Gamrath, Thorsten Koch, Daniel Rehfeldt, Yuji Shinano
Document Type:ZIB-Report
Tag:Branch-and-Cut; DIMACS Challenge; Mixed-Integer Programming; Steiner Tree Problem
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
CCS-Classification:G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.2 Graph Theory (F.2.2) / Trees
G. Mathematics of Computing / G.4 MATHEMATICAL SOFTWARE / Algorithm design and analysis (REVISED)
Date of first Publication:2014/09/24
Series (Serial Number):ZIB-Report (14-35)
ISSN:1438-0064

$Rev: 13581 $