Optimization Online


Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores

Yuji Shinano (shinano***at***zib.de)
Tobias Achterberg (achterberg***at***gurobi.com)
Timo Berthold (TimoBerthold***at***fico.com)
Stefan Heinz (heinz***at***gurobi.com)
Thosten Koch (koch***at***zib.de)
Michael Winkler (winkler***at***gurobi.com)

Abstract: Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.

Keywords: Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Problem Solving Environments )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: ZIB-Report 20-16 (May 2020), Zuse Institute Berlin

Download: [PDF]

Entry Submitted: 05/28/2020
Entry Accepted: 05/28/2020
Entry Last Modified: 06/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society