The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound

accepted for publication on 2017-11-11
  • Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Yuji ShinanoORCiD
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2017
Year of first publication:2017
Preprint:urn:nbn:de:0297-zib-65545