Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs. (English) Zbl 1422.90030

Summary: PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve mixed integer programs (MIPs) with a dual-block angular structure, which is characteristic of deterministic-equivalent stochastic mixed-integer programs. In this paper, we present two different parallelizations of branch & bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator, a universal framework for parallelizing B&B tree search that has been sucessfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.


90C11 Mixed integer programming
90C15 Stochastic programming
Full Text: DOI Link


[1] Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming. Technical report, Technical report 16-44, ZIB, Takustr. 7, 14195 Berlin (2016)
[2] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 42-54, (2005) · Zbl 1076.90037
[3] Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G., Qiu, F., Sen, S.: SIPLIB: a stochastic integer programming test problem library (2018). https://www2.isye.gatech.edu/ sahmed/siplib
[4] Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, ME; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs, Math. Program., 149, 391-424, (2015) · Zbl 1307.90114
[5] Berthold, T.: Primal Heuristics for Mixed Integer Programs. Master’s thesis, TU Berlin (2006)
[6] Butenhof, D.: R: Programming with POSIX Threads. Addison-Wesley Professional, Boston (1997)
[7] Eckstein, J.; Hart, WE; Phillips, CA, PEBBL: an object-oriented framework for scalable parallel branch-and-bound, Math. Program. Comput., 7, 429-469, (2015) · Zbl 1329.90171
[8] Eckstein, J., Phillips, C.A., Hart, W.E.: PEBBL 1.0 User Guide (2007). https://software.sandia.gov/acro/releases/votd/acro/packages/pebbl/doc/uguide/user-guide.pdf
[9] Fischetti, M., Lodi, A.: Heuristics in mixed integer programming. In: Wiley Encyclopedia of Operations Research and Management Science. American Cancer Society (2011). https://doi.org/10.1002/9780470400531.eorms0376
[10] Gamrath, G.; Koch, T.; Martin, A.; Miltenberger, M.; Weninger, D., Progress in presolving for mixed integer programming, Math. Program. Comput., 7, 367-398, (2015) · Zbl 1329.90089
[11] Gropp, W.; Lusk, E.; Doss, N.; Skjellum, A., A high-performance, portable implementation of the MPI message passing interface standard, Parallel Comput., 22, 789-828, (1996) · Zbl 0875.68206
[12] IBM CPLEX optimizer (2018). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/
[13] Kim, K., Zavala, V.: Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Optimization Online (2015) · Zbl 1400.90236
[14] Koch, T.; Ralphs, T.; Shinano, Y., Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 67-93, (2012) · Zbl 1262.90106
[15] Land, AH; Doig, AG, An automatic method of solving discrete programming problems, Econometrica, 28, 497-520, (1960) · Zbl 0101.37004
[16] Linderoth, JT; Savelsbergh, MWP, A computational study of search strategies for mixed integer programming, INFORMS J. Comput., 11, 173-187, (1999) · Zbl 1040.90535
[17] Lubin, M.; Hall, J.; Petra, C.; Anitescu, M., Parallel distributed-memory simplex for large-scale stochastic LP problems, Comput. Optim. Appl., 55, 571-596, (2013) · Zbl 1276.90044
[18] Lubin, M.; Martin, K.; Petra, C.; Sandıkçı, B., On parallelizing dual decomposition in stochastic integer programming, Oper. Res. Lett., 41, 252-258, (2013) · Zbl 1286.90102
[19] Maher, S.J., Fischer, T., Galley, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., Lübbecke, M.E., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 4.0. Technical Report ZIB-Report 17-12, Zuse Institute Berlin (March 2017)
[20] Marchand, H.; Martin, A.; Weismantel, R.; Wolsey, L., Cutting planes in integer and mixed integer programming, Discrete Appl. Math., 123, 397-446, (2002) · Zbl 1130.90370
[21] Munguía, L.-M., Oxberry, G., Rajan, D.: PIPS-SBB: a parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW), pp. 730-739 (May 2016)
[22] Ntaimo, L.; Sen, S., The million-variable “march” for stochastic combinatorial optimization, J. Glob. Optim., 32, 385-400, (2005) · Zbl 1098.90045
[23] Ralphs, T., Shinano, Y., Berthold, T., Koch, T.: Parallel solvers for mixed integer linear programming. Technical Report 16-74, ZIB, Takustr. 7, 14195 Berlin (2016)
[24] Santoso, T.; Ahmed, S.; Goetschalckx, M.; Shapiro, A., A stochastic programming approach for supply chain network design under uncertainty, Eur. J. Oper. Res., 167, 96-115, (2005) · Zbl 1075.90010
[25] Savelsbergh, MWP, Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 445-454, (1994) · Zbl 0814.90093
[26] Shinano, Y.; Achterberg, T.; Berthold, T.; Heinz, S.; Koch, T.; Bischof, C. (ed.); Hegering, HG (ed.); Nagel, WE (ed.); Wittum, G. (ed.), ParaSCIP: a parallel extension of SCIP, 135-148, (2012), Heidelberg
[27] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 770-779. IEEE Computer Society, Los Alamitos (2016)
[28] Shinano, Y.; Fujie, T.; Cappello, F. (ed.); Herault, T. (ed.); Dongarra, J. (ed.), ParaLEX: a parallel extension for the CPLEX mixed integer optimizer, 97-106, (2007), Heidelberg
[29] Shinano, Y.; Heinz, S.; Vigerske, S.; Winkler, M., FiberSCIP—a shared memory parallelization of SCIP, INFORMS J. Comput., 30, 11-30, (2018)
[30] Stoyan, SJ; Kwon, RH, A two-stage stochastic mixed-integer programming approach to the index tracking problem, Optim. Eng., 11, 247-275, (2010) · Zbl 1273.91430
[31] Thakur, R.; Rabenseifner, R.; Gropp, W., Optimization of collective communication operations in MPICH, Int. J. High Perform. Comput. Appl., 19, 49-66, (2005)
[32] UG: Ubiquity Generator framework. http://ug.zib.de/
[33] Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pp. 431-502. Springer Berlin Heidelberg (2010)
[34] Wallace, S., Ziemba, W.: Applications of Stochastic Programming. Society for Industrial and Applied Mathematics, Philadelphia (2005) · Zbl 1068.90002
[35] Watson, J-P; Woodruff, D.; Hart, W., PySP: modeling and solving stochastic programs in Python, Math. Program. Comput., 4, 109-149, (2012) · Zbl 1275.90049
[36] Wojtaszek, DT; Chinneck, JW, Faster MIP solutions via new node selection rules, Comput. Oper. Res., 37, 1544-1556, (2010) · Zbl 1190.90109
[37] Xu, Y.: Scalable Algorithms for Parallel Tree Search. PhD thesis, Lehigh University (2007)
[38] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzmann, M.: ALPS Version 1.5 (2016). https://github.com/coin-or/CHiPPS-ALPS
[39] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzmann, M.: BiCePs Version 0.94 (2017). https://github.com/coin-or/CHiPPS-BiCePS
[40] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzmann, M.: BLIS Version 0.94 (2017). https://github.com/coin-or/CHiPPS-BLIS
[41] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzmann, M.J.: ALPS: a framework for implementing parallel search algorithms. In: The Proceedings of the Ninth INFORMS Computing Society Conference, pp. 319-334 (2005)
[42] Xu, Y.; Ralphs, TK; Ladányi, L.; Saltzmann, MJ, Computational experience with a software framework for parallel integer programming, INFORMS J. Comput., 21, 383-397, (2009) · Zbl 1243.90010
[43] Zheng, QP; Wang, J.; Liu, AL, Stochastic optimization for unit commitment—a review, IEEE Trans. Power Syst., 30, 1913-1924, (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.