Parallel branch-and-bound for two-stage stochastic integer optimization

Akhil Langer, Ramprasad Venkataraman, Udatta Palekar, Laxmikant V. Kale

Research output: Contribution to conferencePaperpeer-review


Many real-world planning problems require searching for an optimal solution in the face of uncertain input. One approach to is to express them as a two-stage stochastic optimization problem where the search for an optimum in one stage is informed by the evaluation of multiple possible scenarios in the other stage. If integer solutions are required, then branch-and-bound techniques are the accepted norm. However, there has been little prior work in parallelizing and scaling branch-and-bound algorithms for stochastic optimization problems. In this paper, we explore the parallelization of a two-stage stochastic integer program solved using branch-and-bound. We present a range of factors that influence the parallel design for such problems. Unlike typical, iterative scientific applications, we encounter several interesting characteristics that make it challenging to realize a scalable design. We present two design variations that navigate some of these challenges. Our designs seek to increase the exposed parallelism while delegating sequential linear program solves to existing libraries. We evaluate the scalability of our designs using sample aircraft allocation problems for the US airfleet. It is important that these problems be solved quickly while evaluating large number of scenarios. Our attempts result in strong scaling to hundreds of cores for these datasets. We believe similar results are not common in literature, and that our experiences will feed usefully into further research on this topic.

Original languageEnglish (US)
Number of pages10
StatePublished - Jan 1 2013
Event20th Annual International Conference on High Performance Computing, HiPC 2013 - Bangalore, India
Duration: Dec 18 2013Dec 21 2013


Other20th Annual International Conference on High Performance Computing, HiPC 2013

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Parallel branch-and-bound for two-stage stochastic integer optimization'. Together they form a unique fingerprint.

Cite this