Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs
epub ahead of print
- PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). 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 (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
Author: | Lluis-Miquel Munguia, Geoffrey Oxberry, Deepak Rajan, Yuji ShinanoORCiD |
---|---|
Document Type: | Article |
Parent Title (English): | Computational Optimization and Applications |
Year of first publication: | 2019 |
Preprint: | urn:nbn:de:0297-zib-65517 |
DOI: | https://doi.org/10.1007/s10589-019-00074-0 |