×

ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers. (English) Zbl 1397.90285

Summary: The Ubiquity Generator ({\mathsf {UG}}) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present {\mathsf{ParaXpress}}, a distributed memory parallelization of the powerful commercial MIP solver {\mathsf{FICO Xpress}}. Besides sheer performance, an important feature of {\mathsf{Xpress}} is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of {\mathsf{ParaXpress}} on a supercomputer, the question arises how to balance the internal {\mathsf{Xpress}} parallelization and the external parallelization by {\mathsf{UG}} against each other. We provide computational experiments to address this question and we show computational results for running {\mathsf{ParaXpress}} on a Top500 supercomputer, using up to 43,344 cores in parallel.

MSC:

90C11 Mixed integer programming
68M14 Distributed systems
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Constraint integer programming, Ph.D. diss., 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] Bussieck, M.R.; Ferris, M.C.; Meeraus, A., grid-enabled optimization with GAMS, INFORMS J. Comput., 21, 349-362, (2009) · Zbl 1243.90255
[4] Performance variability in mixed integer programming, Presentation slides from MIP 2008 workshop in New York City, 2008. Available at
[5] Eckstein, J.; Hart, W.E.; Phillips, C.A., pebbl: an object-oriented framework for scalable parallel branch and bound, Math. Program. Comput., 7, 429-469, (2015) · Zbl 1329.90171
[6] FICO Xpress-Optimizer, Available at
[7] 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. Program. Comput., 3, 103-163, (2011)
[8] 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
[9] Performance variability in mixed-integer programming, in Theory Driven by Influential Applications, H. Topaloglu, ed., INFORMS, Catonsville, MD, 2013, pp. 1-12
[10] Nemhauser, G.L.; Wolsey, L.A., Integer and Combinatorial Optimization, (1988), Wiley, Chichester · Zbl 0469.90052
[11] A dynamic load balancing mechanism for new ParaLEX, in Proceedings of ICPADS 2008, Melbourne, 2008, pp. 455-462
[12] ParaSCIP - a parallel extension of SCIP, in Competence in High Performance Computing 2010, Springer, Berlin, 2012, pp. 135-148
[13] Solving hard MIPLIB2003 problems with ParaSCIP on supercomputers: An update, in Parallel Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International, Phoenix, May, 2014, pp. 1552-1561
[14] A first implementation of ParaXpress: Combining internal and external parallelization to solve MIPs on supercomputers, in Mathematical Software - ICMS 2016: 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings, G.M. Greuel, T. Koch, P. Paule, and A. Sommese, eds., Springer International Publishing, Cham, 2016, pp. 308-316. Available at
[15] Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores, in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE Computer Society, Los Alamitos, CA, 2016, pp. 770-779
[16] Shinano, Y.; Heinz, S.; Vigerske, S.; Winkler, M., fiberscip – a shared memory parallelization of SCIP, INFORMS J. Comput., 30, 1, 11-30, (2018)
[17] Sun, Y.; Zheng, G.; Jetley, P.; Kalé, L.V., parssse: an adaptive parallel state space search engine, Parallel Process. Lett., 21, 319-338, (2011) · Zbl 1253.68062
[18] Alps version 1.5.2, 2015
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.