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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Lluis Miquel Munguia, Geoffrey Oxberry, Deepak Rajan, Yuji Shinano
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