Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs
| Autor: | Geoffrey Oxberry, Deepak Rajan, Lluís-Miquel Munguía, Yuji Shinano |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
021103 operations research
Control and Optimization Generator (computer programming) Applied Mathematics 0211 other engineering and technologies Parallel algorithm 010103 numerical & computational mathematics 02 engineering and technology Parallel computing Solver 01 natural sciences B-tree Computational Mathematics Scalability Parallelism (grammar) 0101 mathematics Layer (object-oriented design) Integer (computer science) Mathematics |
| Zdroj: | Computational Optimization and Applications. 73:575-601 |
| ISSN: | 1573-2894 0926-6003 |
| DOI: | 10.1007/s10589-019-00074-0 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |