Optimization Online


PIPS-SBB: A parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs

Lluis-Miquel Munguia(lluis.munguia***at***gatech.edu)
Geoffrey Oxberry(oxberry1***at***llnl.gov)
Deepak Rajan(rajan3***at***llnl.gov)

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: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels of the optimization process. We show promising results on 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.

Keywords: Keywords: two-stage stochastic mixed-integer programming, distributed memory algorithm, branch and bound, dual block-angular

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 12/22/2015
Entry Accepted: 12/23/2015
Entry Last Modified: 12/22/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society