Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-65517
- 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.
Verfasserangaben: | Lluis-Miquel Munguia, Geoffrey Oxberry, Deepak Rajan, Yuji ShinanoORCiD |
---|---|
Dokumentart: | ZIB-Report |
Ausgabe / Heft: | ZIB-Report 17-58 |
Freies Schlagwort / Tag: | PIPS-SBB, UG, Parallel Branch and Bound |
Psyndex-Schlagwort: | PIPS-SBB, UG, Parallel Branch and Bound |
MSC-Klassifikation: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING | |
CCS-Klassifikation: | G. Mathematics of Computing |
I. Computing Methodologies | |
PACS-Klassifikation: | 00.00.00 GENERAL |
Datum der Erstveröffentlichung: | 11.07.2017 |
Schriftenreihe (Bandnummer): | ZIB-Report (17-58) |
ISSN: | 1438-0064 |
Verlagspublikation: | Computational Optimization and Applications |
DOI: | https://doi.org/10.1007/s10589-019-00074-0 |