1192
eng
reportzib
0
2010-12-21
2010-12-21
--
ParaSCIP - a parallel extension of SCIP
Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.
10-27
10.1007/978-3-642-24025-6_12
http://www.springerlink.com/content/t2160206253v7661/
urn:nbn:de:0297-zib-11921
Bischof, Christian et al. (eds.): Competence in High Performance Computing 2010. Proceedings of an International Conference on Competence in High Performance Computing, June 2010, Schloss Schwetzingen, Germany. Berlin: Springer, 2012, S. 135-148.
Yuji Shinano
-empty- (Opus4 user: admin)
Tobias Achterberg
Stefan Heinz
Timo Berthold
Stefan Heinz
Thorsten Koch
ZIB-Report
10-27
deu
uncontrolled
massive parallization
deu
uncontrolled
mixed integer programming
deu
uncontrolled
ParaSCIP
deu
uncontrolled
branch-and-cut
deu
uncontrolled
branch-and-bound
Mathematical programming methods [See also 90Cxx]
Parallel algorithms
Mixed integer programming
Mathematical Optimization
Achterberg, Tobias
Berthold, Timo
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
https://opus4.kobv.de/opus4-zib/files/1192/ZR-10-27.pdf