2013 61 1 47 78 c 2013 SCIP 1,4 Tobias Achterberg 2 Timo Berthold 1 Stefan Heinz 1 Thorsten Koch 1 Stefan Vigerske 3 Michael Winkler 1 2012 7 2 9 6 10 12 CIP: Constraint Integer Programs CP: Constraint Programming MIP: Mixed Integer Programming SAT: Satisfability Problem 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 SCIP 1. SCIP Solving Constraint Integer Programs, http://scip.zib.de CIP: Constraint Integer Program Achterberg, 2007, 2009 CIP MIP: Mixed Integer Programming : Mixed Integer Linear Programming MIP CIP 2 SCIP MIP H. D. Mittelmann WEB http://plato.asu.edu/bench.html MIP MIP MIP 1 Zuse Institute Berlin, Takustr. 7, D-14195 Berlin-Dahlem, Germany 2 ILOG, IBM Deutschland GmbH, Ober-Eschbacher Str. 109, 61352 Bad Homburg v.d.h., Germany 3 GAMS Software GmbH, P.O. Box 40 59, 50216 Frechen, Germany 4 JST CREST 102 0076 7 K s
48 61 1 2013 10 MIP MIP Gurobi http://www.gurobi. com/ CPLEX http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ Xpress http://www.fico.com/en/products/dmtools/xpress-overview/pages/xpress-optimizer. aspx Koch et al. 2011 10 MIP MIP LP: Linear Programming LP MIP LP LP 2 SCIP 1000 SCIP fast aggressive none SCIP 450,000 CPLEX SCIP 600,000 Achterberg, 2011 MIPLIB Bixby et al., 1992, 1998; Achterberg et al., 2006; Koch et al., 2011 1991 MIPLIB2010 http://miplib.zib.de SCIP
SCIP 49 1. Parallel search tree generated by ParaSCIP and FiberSCIP. SCIP MIP MIP MIP Bixby et al., 1999; Bussieck et al., 2009; Chen and Ferris, 1999; Eckstein, 1997; Phillips et al., 2006; Linderoth, 1998; Ralphs et al., 2003; Shinano et al., 2003, 2007, 2008; Xu et al., 2009 GRID Bussieck et al. 2009 CPLEX CPLEX SCIP MIP Ralphs 2006 2005 CPU CPU Gurobi CPU Gurobi Tree of Trees Concept MIP Shinano et al., 2008 SCIP 1 1 MIP SCIP plug-in MIP plug-in
50 61 1 2013 SCIP SCIP MIPLIB Shinano et al., 2012 2 CIP SCIP 3 SCIP UG Ubiquity Generator UG ParaSCIP FiberSCIP UG 4 MIP 5 2. CIP SCIP 1. CIP: Constraint Integer Program CIP = (C,I,c) : (CIP) c =min{c x C(x), x R n,x j Z for all j I}. C = {C 1,...,C m} C i : R n {0,1} i =1,...,m I N = {1,...,n} c R n CIP : (2.1) ˆx I Z I (A,b ):{x C R C C(ˆx I,x C)} = {x C R C A x C b }. C := N \ I A R k C b R k k Z 0 2.1 LP SCIP MINLP CIP LP MIP C(x)={x R n Ax b} A R m n b R m CIP : (MIP) c =min{c x x R n,x j Z for all j I}. MIP LP : (LP) c =min{c x x R n,ax b}. SCIP Solving Constraint Integer Programs CIP CIP SCIP CIP SCIP plug-in constraint handler C(x) plug-in plug-in
SCIP 51 MIP linear constraint handler LP SCIP LP LP SCIP LP 2 Presolvers: Separators: Propagators: Branching Rules: Node Selectors: Primal Heuristics: Relaxation Handlers: plug-in 2 SCIP LP plug-in plug-in 2. Flowchart of SCIP.
52 61 1 2013 SCIP Conflict Analysis Pricer Conflict Analysis SAT MIP plug-in Pricer CIP SCIP Achterberg 2007 plug-in plug-in SCIP WEB http://scip.zib.de/ 3. UG Ubiquity Generator framework ParaSCIP FiberSCIP SCIP Tree of Trees Concept Ubiquity Generator UG framework MIP Solver Solver 1 Solver Solver Solver UG UG ParaSCIP FiberSCIP UG C++ SCIP UG Ralphs, 2006 1 Ramp-Up Solver 2 Primary Solver Solver 3 Ramp-Down Solver Solver UG Ramp-Up Pthreads MPI Message Passing Interface SCIP UG : ug[ ]
SCIP 53 3. Initialization step. ParaSCIP ug[scip, MPI] FiberSCIP ug[scip, Pthreads] UG 3.1 UG UG ParaSCIP FiberSCIP ParaSCIP 2 MPI FiberSCIP 2 Solver Solver LoadCoordinator LoadCoordinator LoadCoordinator presolve MIP Original instance Presolved instance 3 LoadCoordinator Solver Solver Solver Solver Solver 1 Solver Solver LoadCoordinator LoadCoordinator UG ParaNode ParaNode Solver 1 LoadCoordinator ParaNode Solver Solver ParaNode
54 61 1 2013 Solver ParaNode UG 2 Ramp-Up Normal Ramp-Up. ParaNode Solver ParaNode LoadCoordinator Solver LoadCoordinator ParaNode ParaNode Solver ParaNode Solver Solver ParaNode p ParaNode ParaNode LoadCoordinator Solver GlobalDualBound ParaNode p Solver Ramp-Up Solver ParaNode Racing Ramp-Up. LoadCoordinator ParaNode Solver Solver Solver Solver Solver Solver LoadCoordinator LoadCoordinator Solver Solver ParaNode LoadCoordinator LoadCoordinator Solver Solver Solver Racing Solver Racing 7,000 Solver 7,000 Racing Normal Ramp-Up Racing Ramp-Up Solver Shinano et al. 2008 MIP Solver LoadCoordinator Solver Solver
SCIP 55 Solver LoadCoordinator Solver Solver LoadCoordinator Solver Racing LP Solver LoadCoordinator LoadCoordinator ParaNode BestDualBound BestDualBound Solver LoadCoordinator ParaNode Solver ParaNode Solver Solver LoadCoordinator ParaNode p ParaNode LoadCoordinator Shinano et al. 2008 collecting mode NodeDualBound Solver Global- DualBound LoadCoordinator : (3.1) NodeDualBound GlobalDualBound max{ GlobalDualBound, 1.0} < Threshold ParaNode p LoadCoordinator 3.1 Solver Solver Solver LoadCoordinator 1 ParaNode LoadCoordinator LoadCoordinator ParaNode m p p m p Solver Solver Solver UG LoadCoordinator BestDualBound Solver BestDualBound Solver LoadCoordinator ParaNode Solver ParaNode LoadCoordinator ParaNode ParaNode LoadCoordinator Solver ParaNode Solver ParaNode ParaNode Solver LoadCoordinator ParaNode Solver
56 61 1 2013 ParaNode Solver LoadCoordinator Solver ParaNode Solver 3.2 UG UG LoadCoordinator Solver LoadCoordinator Solver Solver LoadCoordinator LoadCoordinator ParaNode Solver Solver Solver 2009 MIPLIB2003 6 5 1 3.3 ParaSCIP FiberSCIP UG ParaSCIP FiberSCIP Solver FiberSCIP ParaSCIP SCIP
SCIP 57 FiberSCIP SCIP SCIP API Application Program Interface SCIP API SCIP FiberSCIP ParaSCIP SCIP UG UG SCIP SCIP SCIP ParaSCIP FiberSCIP SCIP Solver SCIP SCIP FiberSCIP Solver Solver FiberSCIP ParaSCIP FiberSCIP ParaSCIP 4. MIPLIB2010 Benchmark http://miplib.zib.de/miplib2010-benchmark. php FiberSCIP ParaSCIP 4.1 FiberSCIP MIPLIB2010 Benchmark 87 1 Benchmark MIP 100 1 Vars. Cons. NZs Bin 0-1 Int Cont 1 1 MIP Vars.*Cons. ZIB Alibaba 40 2.5 GHz Quad-Core Xeon E5420 CPU 2 PowerEdgeTM 2950 16GB SCIP 2.1.1 LP SoPlex 1.6.0.1 FiberSCIP 2 Racing Ramp-Up Racing 2 0.5 36 300 Solver 25 1800 Racing Racing FiberSCIP Solver
58 61 1 2013 1. Benchmark set for MIP (MIPLIB2010 Benchmark set).
SCIP 59
60 61 1 2013 2. Sequential executions of SCIP and FiberSCIP.
SCIP 61
62 61 1 2013 SCIP 1 Solver 2GB SCIP Solver 2 SCIP Solver 1 FiberSCIP LoadCoordinator Solver Solver LoadCoordinator Solver Presolve once LoadCoordinator Solver 2 >! 1 Solution Status SCIP FiberSCIP ok ok ok MIPLIB2010 FiberSCIP solved / timelimit / abort 3 3 56 2 2 2 7200 H. D. Mittlemann FiberSCIP SCIP 1 FiberSCIP 1 SCIP Solver LoadCoordinator SCIP SCIP FiberSCIP 2 SCIP 2 47 SCIP FiberSCIP SCIP /FiberSCIP
SCIP 63 4. Relative computing time ratio of FiberSCIP compared to SCIP. 4 4 1 SCIP 2 2 2 1 2 FiberSCIP 2 Racing Solver Solver FiberSCIP Solver Solver Solver 3 Solver 2, 4 6, 8 2 1 Solver Solver Solver Solver Solver Solver Solver Solver 1 Solver 3 4 Solver 8 SCIP 6 Solver 8 Solver 1 Solver 3 i i* i 1, 2, 4, 6 Solver Solver i* 6 Solver Solver Solver 8 Solver
64 61 1 2013 3. Only racing stage runs without upper bounds communications.
SCIP 65
66 61 1 2013 5. Relative computing time ratio of FiberSCIP for each number of Solver threads used. i i* 5 x f(x)=1.0 clog(x) 1 Solver 5 f(x) f(x) c Solver FiberSCIP 1 Solver Solver Solver 1 Solver 5 4 Solver 8 Solver 4 Solver 4 8 Solver 5 5 Solver 5
SCIP 67 4 Solver 5 2 8 Solver 4 Solver 16 1 8 Solver 3 15 Racing Racing Ramp-Up Normal Ramp-Up 2 6 6 2 n Solver FiberSCIP Speedup(n)= FiberSCIP n Solver Settings 58 58 6 2 Load- Coordinator no presolve 1 2 5 LoadCoordinator Solver Solver FiberSCIP Normal Ramp-Up Racing Ramp-Up 6 4 Solver Normal Ramp-Up Racing Ramp-Up 4 Solver Racing Racing Ramp-Up Racing 8 Solver Racing
68 61 1 2013 4. Effects of upper bounds communication (4 Solver Threads).
SCIP 69
表 5. Effects of upper bounds communication (8 Solver Threads). 70 統計数理 第 61 巻 第 1 号 2013
SCIP 71
72 61 1 2013 6. Summary of speedups. Racing Ramp-Up Normal Ramp-Up Normal Ramp-Up Racing Ramp-Up Normal Ramp-Up 4 Solver 8 Solver Racing Ramp-Up Racing Ramp-Up Racing Ramp-Up FiberSCIP MIP H.D.Mittelmann WEB http://plato.asu.edu/bench.html ug[scip/*] MIP WEB MIP
SCIP 73 FiberSCIP MINLP: Mixed Integer Nonlinear Programming SCIP MINLP FiberSCIP 4.2 ParaSCIP ParaSCIP HLRN II https://www.hlrn.de/home/ view 2,048 MIPLIB2003 http://miplib.zib.de/ miplib2003/index.php 2 ds stp3d ds 656 67,732 0-1 stp3d 159,488 204,880 0-1 9 88,388 123,637 0-1 stp3d 10 Shinano et al. 2012 Shinano et al. 2012 ZIB CPLEX stp3d ds 20 CPLEX 12.0 CPLEX ZIB 8 Quad-Core AMD Opteron 8384 2.7 GHz 4 32 512 GB Sun Galaxy 4600 CPLEX ParaSCIP 1 HLRN II ds ParaSCIP HLRN II 1 2,048 12 1 4,096 48 1 ParaSCIP Racing Ramp-Up Racing Ramp-Up 1 Racing Ramp-Up 4,000 1 Solver Solver 1 Solver 1 Solver MPI 1 7 HLRN II 1 stp3d
74 61 1 2013 7. Single job computations. 8. Checkpointing and restarted jobs computation. Solver stp3d 4,096 Normal Ramp-Up 7,168 Racing Ramp-Up Racing Ramp-Up ds 1.4 Solver 4.3 10 7,168 stp3d 5.3 Solver 6.8 8 4,096 7,168 Racing Ramp-Up 4,096 Normal Ramp-Up stp3d Normal Ramp-Up stp3d Normal Ramp-Up Normal Ramp-Up Ramp-Up 1 Solver Racing Ramp-Up Racing Ramp-Up 4,096 1.75 7,168 stp3d 1.34 1 Shinano et al. 2012 ds 16 17 86 1 1 8 Time[h] 1 96 1 181,248 4,096 1 1
SCIP 75 4,096 76 = 311,296 1 8 12 1 1 1 1000 Solver Solver 1 MIPLIB2010 ParaSCIP Koch et al. 2011 4 http://miplib.zib.de/ News ParaSCIP Distributed-memory supercomputer Fujitsu PRIMERGY RX200S5 LP CPLEX 12.3 MIPLIB2010 dg012142 6,310 640 0-1 1,440 MIP 256 42 1 941,693,415 2,300,867 MIPLIB2010 5. SCIP SCIP MIP FiberSCIP SCIP MIP MINLP FiberSCIP ParaSCIP MIP SCIP
76 61 1 2013 H. D. Mittelmann FiberSCIP ParaSCIP SCIP Optimization Suite Solver FiberSCIP ParaSCIP Thorsten Koch Google Research Grant JST CREST : HLRN II HPC ZIB HPC Achterberg, T. 2007. Constraint Integer Programming, Ph.D. Thesis, Technische Universität Berlin. Achterberg, T. 2009. SCIP: Solving constraint integer programs, Mathematical Programming Computation, 1 1 1 41. Achterberg, T. 2011. Comparing SCIP to CPLEX, INFORMS 2011 Annual Meeting. Achterberg, T., Koch, T.and Martin, A. 2006. MIPLIB 2003, Operations Research Letters, 34 4 361 372. Bixby, R. E., Boyd, E. A.and Indovina, R. R. 1992. MIPLIB: A test set of mixed integer programming problems, SIAM News, 25, p.16. Bixby, R.E., Ceria, S., McZeal, C.and Savelsbergh, M. 1998. An updated mixed integer programming library: MIPLIB 3.0, Optima, 58, 12 15. Bixby,R.E.,Cook,W.,Cox,A.andLee,E.K. 1999. Computational experience with parallel mixed integer programming in a distributed environment, Annals of Operations Research, 90, 19 43. Bussieck, M. R., Ferris, M. C. and Meeraus, A. 2009. Grid enabled optimization with GAMS, INFORMS Journal on Computing, 21 3 349 362.
SCIP 77 Chen, Q. and Ferris, M. C. 1999. FATCOP: A fault tolerant condor-pvm mixed integer program solver, Mathematical Programming Technical Report 99 05, Madison. Eckstein, J. 1997. Distributed versus centralized storage and control for parallel branch and bound: Mixed integer programming on the CM-5, Computational Optimization and Applications, 7 2 199 220. Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R. E., Danna, E., Gamrath, G., Gleixner, A. M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T. K., Salvagnin, D., Steffy, D. E. and Wolter, K. 2011. MIPLIB 2010, Mathematical Programming Computation, 3, 103 163. Linderoth, J. T. 1998. Topics in parallel integer optimization, Ph.D. Thesis, Georgia Institute of Technology. Phillips, C., Eckstein, J. and Hart, W. 2006. Massively parallel mixed-integer programming: Algorithms and applications, Parallel Processing for Scientific Computing eds. M. Heroux, P. Raghavan and H. Simon 323 340. Ralphs, T. K. 2006. Parallel Combinatorial Optimization, Chapter 3, 53 101, Wiley, Hoboken, New Jersey. Ralphs, T. K., Ládanyi, L. and Saltzman, M. J. 2003. Parallel branch, cut and price for large-scale discrete optimization, Mathematical Programming, 98, 253 280. Shinano, Y. and Fujie, T. 2007. ParaLEX: A parallel extension for the CPLEX mixed integer optimizer, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science, Vol. 4757, 97 106, Springer, Berlin, Heidelberg. Shinano, Y., Fujie, T. and Kounoike, Y. 2003. Effectiveness of parallelizing the ILOG-CPLEX mixed integer optimizer in the PUBB2 framework, Euro-Par 2003 Parallel Processing, Lecture Notes in Computer Science, Vol. 2790, 451 460, Springer, Berlin, Heidelberg. Shinano, Y., Achterberg, T. and Fujie, T. 2008. A dynamic load balancing mechanism for new ParaLEX, 14th IEEE International Conference on Parallel and Distributed Systems (IC- PADS 08), 455 462. Shinano, Y., Achterberg, T., Berthold, T., Heinz, S. and Koch, T. 2012. ParaSCIP A parallel extension of SCIP, Competence in High Performance Computing 2010 eds. Bischof, C., Hegering, H. G., Nagel, W. E., Wittum, G. 135 148, Springer, Berlin, Heidelberg. Xu,Y.,Ralphs,T.K.,Ladányi, L. and Saltzman, M. J. 2009. Computational experience with a software framework for parallel integer programming, INFORMS Journal on Computing, 21, 383 397.
78 Proceedings of the Institute of Statistical Mathematics Vol. 61, No. 1, 47 78 (2013) Parallelizing the Constraint Integer Programming Solver SCIP Yuji Shinano 1,4,TobiasAchterberg 2,TimoBerthold 1,StefanHeinz 1, Thorsten Koch 1,StefanVigerske 3 and Michael Winkler 1 1 Zuse Institute Berlin 2 ILOG, IBM Deutschland GmbH 3 GAMS Software GmbH 4 JST CREST The paradigm of constraint integer programming (CIP) combines modeling and solving techniques from the fields of constraint programming (CP), mixed-integer programming (MIP) and satisfability problem (SAT). This paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now being 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 a shared memory computing environment. ParaSCIP has been run successfully 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. Key words: Mixed integer programming, constraint integer programming, SCIP, parallelization.