FiberSCIP—A Shared Memory Parallelization of SCIP

Yuji Shinano (), Stefan Heinz (), Stefan Vigerske () and Michael Winkler ()
Additional contact information
Yuji Shinano: Zuse Institute Berlin, Berlin 14195, Germany
Stefan Heinz: Fair Isaac Germany GmbH, Berlin 14195, Germany
Stefan Vigerske: GAMS Software GmbH, Berlin 14195, Germany
Michael Winkler: Gurobi GmbH, Berlin 14195, Germany

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 11-30

Abstract: Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel.

Keywords: parallel; branch-and-bound; deterministic parallelism; constraint integer programming; mixed integer programming; mixed integer nonlinear programming; SCIP; MIP; MINLP (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0762 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:11-30

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().