TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update N2 - Contemporary supercomputers can easily provide years of CPU time per wall-clock hour. One challenge of today's software development is how to harness this wast computing power in order to solve really hard mixed integer programming instances. In 2010, two out of six open MIPLIB2003 instances could be solved by ParaSCIP in more than ten consecutive runs, restarting from checkpointing files. The contribution of this paper is threefold: For the first time, we present computational results of single runs for those two instances. Secondly, we provide new improved upper and lower bounds for all of the remaining four open MIPLIB2003 instances. Finally, we explain which new developments led to these results and discuss the current progress of ParaSCIP. Experiments were conducted on HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores. T3 - ZIB-Report - 13-66 KW - Mixed Integer Programming KW - MIPLIB2003 KW - ParaSCIP KW - Ubiquity Generator Framework KW - Supercomputer Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42888 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - 制約整数計画ソルバ SCIP の並列化 T1 - Parallelizing the Constraint Integer Programming Solver SCIP N2 - 制約整数計画(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に最適解を与えた. N2 - 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. T2 - Parallelizing the Constraint Integer Programming Solver SCIP T3 - ZIB-Report - 13-22 KW - Mixed Integer Programming KW - Constraint Integer Programming KW - Parallel Computing KW - Distributed Memory Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18130 SN - 1438-0064 ER -