Operations Research Seminar: Yuji Shinano

November 14, 2017

4:30 PM

CORE (room b-135)

Harnessing over a Million CPU Cores to Solve a Single Hard Mixed Integer Programming Problem on a Supercomputer

Yuji Shinano, Zuse Institute Berlin

Mixed integer programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers, software packages to solve MIPs, 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 of supercomputers. Additionally, a specialized version of ParaSCIP for solving Steiner tree problems called SCIP-Jack solved three open instances from the Steiner tree test benchmark set PUC. 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 solvers. The UG framework is currently being used to develop ParaXpress, a distributed memory parallelization of the commercial MIP solver Xpress. Moreover, it is being used to parallelize PIPS-SBB, a solver for stochastic MIPs. Since Xpress is a multi-threaded solver and ParaSCIP can run at least 80,000 processes in parallel for solving a single MIP, ParaXpress could handle over a million CPU cores. Furthermore, the parallelization of PIPS-SBB by the UG framework has the potential to also handle over a million CPU cores. In this talk, a ground design of the UG framework and its latest extensions to harness over a million CPU cores will be presented and preliminary computational results will be provided.

Categories Events: