## 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 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 |