04_toukei01.dvi

Size: px

Start display at page:

Download "04_toukei01.dvi"

而否孙
5 years ago
Views:

1 c 2013 SCIP 1,4 Tobias Achterberg 2 Timo Berthold 1 Stefan Heinz 1 Thorsten Koch 1 Stefan Vigerske 3 Michael Winkler 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 dg SCIP 1. SCIP Solving Constraint Integer Programs, 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 MIP MIP MIP 1 Zuse Institute Berlin, Takustr. 7, D Berlin-Dahlem, Germany 2 ILOG, IBM Deutschland GmbH, Ober-Eschbacher Str. 109, Bad Homburg v.d.h., Germany 3 GAMS Software GmbH, P.O. Box 40 59, Frechen, Germany 4 JST CREST K s

2 MIP MIP Gurobi com/ CPLEX Xpress aspx Koch et al 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., MIPLIB 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.

3 SCIP 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 CPLEX CPLEX SCIP MIP Ralphs CPU CPU Gurobi CPU Gurobi Tree of Trees Concept MIP Shinano et al., 2008 SCIP 1 1 MIP SCIP plug-in MIP plug-in

4 SCIP SCIP MIPLIB Shinano et al., 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 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

5 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.

6 SCIP Conflict Analysis Pricer Conflict Analysis SAT MIP plug-in Pricer CIP SCIP Achterberg 2007 plug-in plug-in SCIP WEB 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, Ramp-Up Solver 2 Primary Solver Solver 3 Ramp-Down Solver Solver UG Ramp-Up Pthreads MPI Message Passing Interface SCIP UG : ug[ ]

7 SCIP 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

8 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 MIP Solver LoadCoordinator Solver Solver

9 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 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

10 ParaNode Solver LoadCoordinator Solver ParaNode Solver 3.2 UG UG LoadCoordinator Solver LoadCoordinator Solver Solver LoadCoordinator LoadCoordinator ParaNode Solver Solver Solver 2009 MIPLIB ParaSCIP FiberSCIP UG ParaSCIP FiberSCIP Solver FiberSCIP ParaSCIP SCIP

11 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 php FiberSCIP ParaSCIP 4.1 FiberSCIP MIPLIB2010 Benchmark 87 1 Benchmark MIP Vars. Cons. NZs Bin 0-1 Int Cont 1 1 MIP Vars.*Cons. ZIB Alibaba GHz Quad-Core Xeon E5420 CPU 2 PowerEdgeTM GB SCIP LP SoPlex FiberSCIP 2 Racing Ramp-Up Racing Solver Racing Racing FiberSCIP Solver

12 Benchmark set for MIP (MIPLIB2010 Benchmark set).

13 SCIP 59

14 Sequential executions of SCIP and FiberSCIP.

15 SCIP 61

16 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 H. D. Mittlemann FiberSCIP SCIP 1 FiberSCIP 1 SCIP Solver LoadCoordinator SCIP SCIP FiberSCIP 2 SCIP 2 47 SCIP FiberSCIP SCIP /FiberSCIP

17 SCIP Relative computing time ratio of FiberSCIP compared to SCIP SCIP FiberSCIP 2 Racing Solver Solver FiberSCIP Solver Solver Solver 3 Solver 2, 4 6, 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

18 Only racing stage runs without upper bounds communications.

19 SCIP 65

20 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

21 SCIP 67 4 Solver Solver 4 Solver Solver 3 15 Racing Racing Ramp-Up Normal Ramp-Up n Solver FiberSCIP Speedup(n)= FiberSCIP n Solver Settings Load- Coordinator no presolve 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

22 Effects of upper bounds communication (4 Solver Threads).

23 SCIP 69

24 表 5. Eﬀects of upper bounds communication (8 Solver Threads). 70 統計数理第 61 巻第 1 号 2013

25 SCIP 71

26 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 ug[scip/*] MIP WEB MIP

27 SCIP 73 FiberSCIP MINLP: Mixed Integer Nonlinear Programming SCIP MINLP FiberSCIP 4.2 ParaSCIP ParaSCIP HLRN II view 2,048 MIPLIB miplib2003/index.php 2 ds stp3d ds , stp3d 159, , , , stp3d 10 Shinano et al Shinano et al ZIB CPLEX stp3d ds 20 CPLEX 12.0 CPLEX ZIB 8 Quad-Core AMD Opteron GHz GB Sun Galaxy 4600 CPLEX ParaSCIP 1 HLRN II ds ParaSCIP HLRN II 1 2, , 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

28 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 ,168 stp3d 5.3 Solver ,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, ,168 stp3d Shinano et al ds Time[h] ,248 4,

29 SCIP 75 4, = 311, Solver Solver 1 MIPLIB2010 ParaSCIP Koch et al News ParaSCIP Distributed-memory supercomputer Fujitsu PRIMERGY RX200S5 LP CPLEX 12.3 MIPLIB2010 dg , ,440 MIP ,693,415 2,300,867 MIPLIB SCIP SCIP MIP FiberSCIP SCIP MIP MINLP FiberSCIP ParaSCIP MIP SCIP

30 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 Constraint Integer Programming, Ph.D. Thesis, Technische Universität Berlin. Achterberg, T SCIP: Solving constraint integer programs, Mathematical Programming Computation, Achterberg, T Comparing SCIP to CPLEX, INFORMS 2011 Annual Meeting. Achterberg, T., Koch, T.and Martin, A MIPLIB 2003, Operations Research Letters, Bixby, R. E., Boyd, E. A.and Indovina, R. R MIPLIB: A test set of mixed integer programming problems, SIAM News, 25, p.16. Bixby, R.E., Ceria, S., McZeal, C.and Savelsbergh, M An updated mixed integer programming library: MIPLIB 3.0, Optima, 58, Bixby,R.E.,Cook,W.,Cox,A.andLee,E.K Computational experience with parallel mixed integer programming in a distributed environment, Annals of Operations Research, 90, Bussieck, M. R., Ferris, M. C. and Meeraus, A Grid enabled optimization with GAMS, INFORMS Journal on Computing,

31 SCIP 77 Chen, Q. and Ferris, M. C FATCOP: A fault tolerant condor-pvm mixed integer program solver, Mathematical Programming Technical Report 99 05, Madison. Eckstein, J Distributed versus centralized storage and control for parallel branch and bound: Mixed integer programming on the CM-5, Computational Optimization and Applications, 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 MIPLIB 2010, Mathematical Programming Computation, 3, Linderoth, J. T Topics in parallel integer optimization, Ph.D. Thesis, Georgia Institute of Technology. Phillips, C., Eckstein, J. and Hart, W Massively parallel mixed-integer programming: Algorithms and applications, Parallel Processing for Scientific Computing eds. M. Heroux, P. Raghavan and H. Simon Ralphs, T. K Parallel Combinatorial Optimization, Chapter 3, , Wiley, Hoboken, New Jersey. Ralphs, T. K., Ládanyi, L. and Saltzman, M. J Parallel branch, cut and price for large-scale discrete optimization, Mathematical Programming, 98, Shinano, Y. and Fujie, T 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, , Springer, Berlin, Heidelberg. Shinano, Y., Fujie, T. and Kounoike, Y 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, , Springer, Berlin, Heidelberg. Shinano, Y., Achterberg, T. and Fujie, T A dynamic load balancing mechanism for new ParaLEX, 14th IEEE International Conference on Parallel and Distributed Systems (IC- PADS 08), Shinano, Y., Achterberg, T., Berthold, T., Heinz, S. and Koch, T ParaSCIP A parallel extension of SCIP, Competence in High Performance Computing 2010 eds. Bischof, C., Hegering, H. G., Nagel, W. E., Wittum, G , Springer, Berlin, Heidelberg. Xu,Y.,Ralphs,T.K.,Ladányi, L. and Saltzman, M. J Computational experience with a software framework for parallel integer programming, INFORMS Journal on Computing, 21,

32 78 Proceedings of the Institute of Statistical Mathematics Vol. 61, No. 1, (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 dg from MIPLIB2010 was solved by using the ISM supercomputer. Key words: Mixed integer programming, constraint integer programming, SCIP, parallelization.

和文タイトル

和文タイトル - Bus Timetable Design to Ensure Smooth Transfer and Avoid Delay Propagation - An Application of Optimization Techniques to Design of Public Transport Services in Fuji City * ** *** ** Takehiro TANAKA*,