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 library 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.