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.
| Author: | Gerald GamrathORCiD, Thorsten KochORCiD, Daniel RehfeldtORCiD, Yuji ShinanoORCiD |
|---|---|
| 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 |
