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

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

Research output: Contribution to conferencePaper

Abstract

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)
Pages266-275
Number of pages10
DOIs
StatePublished - Jan 1 2013
Event20th Annual International Conference on High Performance Computing, HiPC 2013 - Bangalore, India
Duration: Dec 18 2013Dec 21 2013

Other

Other20th Annual International Conference on High Performance Computing, HiPC 2013
CountryIndia
CityBangalore
Period12/18/1312/21/13

    Fingerprint

ASJC Scopus subject areas

  • Software

Cite this

Langer, A., Venkataraman, R., Palekar, U., & Kale, L. V. (2013). Parallel branch-and-bound for two-stage stochastic integer optimization. 266-275. Paper presented at 20th Annual International Conference on High Performance Computing, HiPC 2013, Bangalore, India. https://doi.org/10.1109/HiPC.2013.6799130