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

Please always quote using this URN: urn:nbn:de:0297-zib-65545
  • 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.

Download full text files

Export metadata

Metadaten
Author:Yuji Shinano
Document Type:ZIB-Report
Tag:Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack
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:D. Software
PACS-Classification:00.00.00 GENERAL
Date of first Publication:2017/07/11
Series (Serial Number):ZIB-Report (17-60)
ISSN:1438-0064