Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores
- SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best-known solutions to instances from the benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
Author: | Yuji ShinanoORCiD, Daniel RehfeldtORCiD, Thorsten KochORCiD |
---|---|
Document Type: | In Proceedings |
Parent Title (English): | Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019 |
Volume: | 11494 |
First Page: | 529 |
Last Page: | 539 |
Series: | LNCS |
Publisher: | Springer |
Year of first publication: | 2019 |
Preprint: | urn:nbn:de:0297-zib-71118 |
DOI: | https://doi.org/10.1007/978-3-030-19212-9_35 |