×

Parallelization of the FICO Xpress-Optimizer. (English) Zbl 1434.90003

Greuel, Gert-Martin (ed.) et al., Mathematical software – ICMS 2016. 5th international conference, Berlin, Germany, July 11–14, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9725, 251-258 (2016).
Summary: Many optimization problems arising in practice can be modeled as mixed integer programs (MIPs). In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. A natural precondition to achieving reasonabling speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for mathematical optimization software; solvers like the FICO Xpress-Optimizer are expected to be deterministic. The resulting synchronization latencies 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 scaling on modern high-performance CPUs. As an added value, the solution path that the FICO Xpress-Optimizer takes is not only deterministic in a fixed environment, but, to a certain extent, thread-independent.
For the entire collection see [Zbl 1342.68017].

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
68W10 Parallel algorithms in computer science
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T.: Constraint integer programming. Technische Universität Berlin (2007) · Zbl 1169.90414
[2] Dantzig, G., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960) · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[3] FICO Xpress-Optimizer, Reference Manual. http://www.fico.com/xpress
[4] Fischetti, M., Lodi, A., Monaci, M., Salvagnin, D., Tramontani, A.: Improving branch-and-cut performance by random sampling. Math. Programm. Comput. 1–20 (2015) · Zbl 1334.90079
[5] Fischetti, M., Monaci, M., Salvagnin, D.: Self-splitting of workload in parallel computation. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 394–404. Springer, Heidelberg (2014) · Zbl 06298806 · doi:10.1007/978-3-319-07046-9_28
[6] Huangfu, Q., Hall, J.: Parallelizing the dual revised simplex method. Technical report 1503.01889, ArXiv e-prints (2015) · Zbl 1317.90189
[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. Progam. Comput. 3, 103–163 (2011) · Zbl 06110465 · doi:10.1007/s12532-011-0025-9
[8] Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497–520 (1960) · Zbl 0101.37004 · doi:10.2307/1910129
[9] Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study. Inf. J. Comput. 21(2), 304–313 (2009) · Zbl 1243.90149 · doi:10.1287/ijoc.1080.0293
[10] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067 · doi:10.1002/9781118627372
[11] Ralphs, T.K., Ladányi, L., Saltzman, M.J.: Parallel branch, cut and price for large-scale discrete optimization. Math. Program. B 98(1–3), 253–280 (2003) · Zbl 1082.90102 · doi:10.1007/s10107-003-0404-8
[12] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP: a parallel extension of SCIP. Competence in High Performance Computing 2010, pp. 135–148. Springer, Heidelberg (2011) · doi:10.1007/978-3-642-24025-6_12
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.