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.

Additional Services

Author: Gerald Gamrath, Thorsten Koch, Daniel Rehfeldt, Yuji Shinano ZIB-Report Branch-and-Cut; DIMACS Challenge; Mixed-Integer Programming; Steiner Tree Problem 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 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) 2014/09/24 ZIB-Report (14-35) 1438-0064

$Rev: 13581$