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 |

