Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs

Please always quote using this 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.

Download full text files

Export metadata

Author:Lluis-Miquel Munguia, Geoffrey Oxberry, Deepak Rajan, Yuji Shinano
Document Type:ZIB-Report
Issue:ZIB-Report 17-58
Tag:PIPS-SBB, UG, Parallel Branch and Bound
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
CCS-Classification:G. Mathematics of Computing
I. Computing Methodologies
PACS-Classification:00.00.00 GENERAL
Date of first Publication:2017/07/11
Series (Serial Number):ZIB-Report (17-58)