• search hit 1 of 39
Back to Result List

Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores

Please always quote using this URN: urn:nbn:de:0297-zib-71118
  • 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 par- allel 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 bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably 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.

Download full text files

Export metadata

Metadaten
Author:Yuji ShinanoORCiD, Daniel RehfeldtORCiD, Thorsten KochORCiD
Document Type:ZIB-Report
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:I. Computing Methodologies
Date of first Publication:2018/12/07
Series (Serial Number):ZIB-Report (18-58)
ISSN:1438-0064