×

zbMATH — the first resource for mathematics

Parallelization of the FICO Xpress-Optimizer. (English) Zbl 1397.90277
Summary: Computing hardware has mostly thrashed out the physical limits for speeding up individual computing cores. Consequently, the main line of progress for new hardware is growing the number of computing cores within a single CPU. This makes the study of efficient parallelization schemes for computation-intensive algorithms more and more important. A natural precondition to achieving reasonable speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for software that is used in industrial applications. In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. MIP solvers like Xpress are expected to be deterministic. This inevitably results in synchronization latencies which render the goal of a satisfying workload a challenge in itself. We address this challenge by following a partial information approach and separating the concepts of simultaneous tasks and independent threads from each other. Our computational results indicate that this leads to a much higher CPU workload and thereby to an improved, almost linear, scaling on modern high-performance CPUs. As an added value, the solution path that Xpress takes is not only deterministic in a fixed environment, but also, to a certain extent, thread-independent. This paper is an extended version of T. Berthold et al. [Lect. Notes Comput. Sci. 9725, 251–258 (2016; Zbl 1434.90003)] containing more detailed technical descriptions, illustrative examples and updated computational results.
MSC:
90C11 Mixed integer programming
68W10 Parallel algorithms in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Constraint Integer Programming, Technische Universität Berlin, 2007
[2] Mixed integer programming: Analyzing 12 years of progress, in Facets of Combinatorial Optimization - Festschrift for Martin Grötschel, M. Jünger and G. Reinelt, eds., Springer, Berlin, 2013, pp. 449-481 · Zbl 1317.90206
[3] Machine learning to balance the load in parallel branch-and-bound, Tech. rep., Optimization Online, 2014
[4] Parallelization of the FICO Xpress-Optimizer, in Mathematical Software - ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommere, eds., Springer International Publishing, Berlin, 2016, pp. 251-258
[5] Bixby, R.E.; Cook, W.; Cox, A.; Lee, E.K., computational experience with parallel mixed integerprogramming in a distributed environment, Ann. Oper. Res., 90, 19-43, (1999) · Zbl 0937.90073
[6] Bussieck, M.R.; Ferris, M.C.; Meeraus, A., grid-enabled optimization with gams, INFORMS J. Comput., 21, 349-362, (2009) · Zbl 1243.90255
[7] Chen, Q.; Ferris, M.C.; Linderoth, J., fatcop 2.0: advanced features in an opportunistic mixed integer programming solver, Ann. Oper. Res., 103, 17-32, (2001) · Zbl 1039.90046
[8] Dantzig, G.B.; Wolfe, P., decomposition principle for linear programs, Oper. Res., 8, 101-111, (1960) · Zbl 0093.32806
[9] Eckstein, J., parallel branch-and-bound algorithms for general mixed integer programming on the cm-5, SIAM J. Optim., 4, 794-814, (1994) · Zbl 0819.90063
[10] Eckstein, J.; Phillips, C.A.; Hart, W.E., pico: an object-oriented framework for parallel branch and bound, Stud. Comput. Math., 8, 219-265, (2001) · Zbl 0989.90130
[11] FICO Xpress-Optimizer, Reference Manual, Available at
[12] Self-splitting of workload in parallel computation, in Integration of AI and OR Techniques in Constraint Programming, H. Simonis, ed., Springer, Cork, 2014, pp. 394-404 · Zbl 06298806
[13] Fischetti, M.; Lodi, A.; Monaci, M.; Salvagnin, D.; Tramontani, A., improving branch-and-cut performance by random sampling, Math. Program. Comput., 1-20, (2015)
[14] Distributed domain propagation, Tech. Rep. 16-71, ZIB, Takustr.7, 14195 Berlin, 2016
[15] Parallelizing the dual revised simplex method, Tech. Rep. 1503.01889, ArXiv e-prints, 2015
[16] 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.; Salvagnin, D.; Steffy, D.E.; Wolter, K., MIPLIB 2010, Math. Progam. Comput., 3, 103-163, (2011)
[17] Land, A.H.; Doig, A.G., an automatic method of solving discrete programming problems, Econometrica, 28, 497-520, (1960) · Zbl 0101.37004
[18] Laundy, R.; Perregaard, M.; Tavares, G.; Tipi, H.; Vazacopoulos, A., solving hard mixed-integer programming problems with xpress-MP: A MIPLIB 2003 case study, INFORMS J. Comput., 21, 304-313, (2009) · Zbl 1243.90149
[19] Topics in parallel integer optimization, Ph.D. thesis, Georgia Institute of Technology, 1998
[20] Mitra, G.; Hai, I.; Hajian, M.T., A distributed processing algorithm for solving integer programs using a cluster of workstations, Parallel Comput., 23, 733-753, (1997) · Zbl 0907.68022
[21] Integer and combinatorial optimisationWileyChichester1988
[22] Nwana, V.; Darby-Dowman, K.; Mitra, G., A two-stage parallel branch and bound algorithm for mixed integer programs, IMA J. Manage. Math., 15, 227-242, (2004) · Zbl 1070.90077
[23] Olszewski, M.; Ansel, J.; Amarasinghe, S., kendo: efficient deterministic multithreading in software, ACM Sigplan Notices, 44, 97-108, (2009)
[24] Ralphs, T., parallel branch and cut, Parallel Combin Optim., 58, 53, (2006)
[25] Ralphs, T.K.; Ladányi, L.; Saltzman, M.J., parallel branch, cut and price for large-scale discrete optimization, Math. Program. B, 98, 253-280, (2003) · Zbl 1082.90102
[26] Parallel solvers for mixed integer linear programming, Tech. Rep. 16-74, ZIB, Takustr.7, 14195 Berlin, 2016
[27] ParaLEX: A parallel extension for the CPLEX mixed integer optimizer, in European Parallel Virtual Machine/Message Passing Interface Users’ Group Meeting, F. Cappello, T. Herald, and J. Dongarra, eds., Springer, Paris, 2007, pp. 97-106
[28] ParaSCIP: A parallel extension of SCIP, in Competence in High Performance Computing 2010, C. Bischof, H.-G., Hegering, W.E. Nagel, and G. Wittum, eds., Springer, Berlin, 2011, pp. 135-148
[29] Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update, in Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International, IEEE, 2014, pp. 1552-1561
[30] Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores, Tech. rep., ZR 15-53, ZIB, Takustr. 7, 14195 Berlin, 2015. Accepted to IPDPS, 2016
[31] A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers, in Mathematical Software - ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommese, eds., Springer International Publishing, Berlin, 2016, pp. 308-316 · Zbl 1434.90006
[32] Integer Programming, Wiley, Chichester, 1998 · Zbl 0930.90072
[33] Xu, Y.; Ralphs, T.K.; Ladányi, L.; Saltzman, M.J., computational experience with a software framework for parallel integer programming, INFORMS J. Comput., 21, 383-397, (2009) · Zbl 1243.90010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.