EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1900. Finding optimal solutions to previously unsolved combinatorial optimization problems by using more than 100,000 cores

Invited abstract in session TA-30: Parallel Solvers, stream Software for Optimization.

Tuesday, 8:30-10:00
Room: 064 (building: 208)

Authors (first author is the speaker)

1. Yuji Shinano
Optimization, Zuse Institue Berlin

Abstract

The Ubiquity Generator framework (UG) was originally designed to parallelize powerful state-of-the-art branch-and-bound based solvers (we call these “base solvers”). Two of the most intensively developed parallel solvers are FiberSCIP (for a shared memory computing environment) and ParaSCIP (for a distributed computing environment). Both of which use SCIP as the base solver. Since debugging on distributed environments is inefficient, FiberSCIP was developed, which has the same parallelization algorithms as ParaSCIP (since UG abstracts the parallelization library) but can run on a single PC. Due to the major debugging effort of UG and SCIP via FiberSCIP, ParaSCIP could solve more than 20 open instances from MIPLIB by using up to 80,000 cores and none of these results has been proven wrong so far. Since UG provides a systematic way to parallelize a state-of-the-art sequential or multi-threaded solver to run on a large-scale distributed memory environment, with version 1.0, UG is generalized to a software framework for high-level task parallelization. That is, with version 1.0, UG will not only parallelize the tree search of branch-and-bound-based solvers but allow the parallelization of other kinds of solvers. In this talk, we present the latest status for exactly solving previously unsolved instances of combinatorial optimization problems.

Keywords

Status: accepted

Back to the list of papers