The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound
2018; Springer Nature; Linguagem: Inglês
10.1007/978-3-319-89920-6_20
ISSN2197-9294
Autores Tópico(s)Formal Methods in Verification
ResumoMixed integer linear programming (MILP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MILP 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 MILP 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.
Referência(s)