PIPS-SBB: A Parallel Distributed-Memory Branch-and-Bound Algorithm for Stochastic Mixed-Integer Programs

Abstract

Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed-integer programs, problem instances can exceed available memory on a single workstation. To overcome this limitation, we present PIPS-SBB: an exact distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels of the optimization process. We show promising results on instances from the SIPLIB benchmark by combining methods known for accelerating Branch and Bound (B&B) methods with new ideas that leverage the structure of SMIPs. We expect the performance of PIPS-SBB to improve further as more functionality is added in the future.