制約整数計画ソルバ SCIP の並列化

Parallelizing the Constraint Integer Programming Solver SCIP

Please always quote using this URN: urn:nbn:de:0297-zib-18130
  • 制約整数計画(CIP: Constraint Integer Programming)は,制約プログラミング(CP: Constraint Programming), 混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究 分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を 扱うことができる.SCIP (Solving Constraint Integer Programs)は,CIPを解くソルバとして実装され, Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では, 著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する. 一つは,複数計算ノード間で大規模に並列動作するParaSCIP である. もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作するFiberSCIP である. ParaSCIP は,HLRN IIスーパーコンピュータ上で, 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また, 統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある. 統計数理研究所のFujitsu PRIMERGY RX200S5上 では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスであるdg012142に最適解を与えた.
  • The paradigm of Constraint Integer Programming (CIP) combines modeling and solving techniques from the fields of Constraint Programming (CP), Mixed Integer Programming (MIP) and Satisfiability Problems (SAT). The paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on shared memory computing environments. ParaSCIP has successfully been run on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, Stefan Vigerske, Michael Winkler
Document Type:ZIB-Report
Tag:Constraint Integer Programming; Distributed Memory; Mixed Integer Programming; Parallel Computing
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Wxx Algorithms (For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx) / 68W10 Parallel algorithms
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
Date of first Publication:2013/04/22
Series (Serial Number):ZIB-Report (13-22)
ISSN:1438-0064
Licence (German):License LogoCreative Commons - Namensnennung

$Rev: 13581 $