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

  • 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
First Page:143
Last Page:149
Publisher:Springer International Publishing
Year of first publication:2018
Pagenumber:6
Preprint:urn:nbn:de:0297-zib-65545
DOI:https://doi.org/10.1007/978-3-319-89920-6_20