4259
eng
reportzib
0
2013-09-27
2013-09-27
--
FiberSCIP - A shared memory parallelization of SCIP
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 MIP 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, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
1438-0064
urn:nbn:de:0297-zib-42595
10.1287/ijoc.2017.0762
INFORMS Journal on Computing
Yuji Shinano
Yuji Shinano
Stefan Heinz
Stefan Vigerske
Michael Winkler
ZIB-Report
13-55
eng
uncontrolled
parallel
eng
uncontrolled
branch-and-bound
eng
uncontrolled
deterministic parallelism
eng
uncontrolled
constraint integer programming
eng
uncontrolled
mixed integer programming
eng
uncontrolled
mixed integer nonlinear programming
eng
uncontrolled
SCIP
eng
uncontrolled
MIP
eng
uncontrolled
MINLP
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Heinz, Stefan
Shinano, Yuji
Vigerske, Stefan
Winkler, Michael
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev3.pdf