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

Akhil Langer, Ramprasad Venkataraman, Udatta S 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

Scalability
Aircraft
Planning

ASJC Scopus subject areas

  • Software

Cite this

Langer, A., Venkataraman, R., Palekar, U. S., & 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

Parallel branch-and-bound for two-stage stochastic integer optimization. / Langer, Akhil; Venkataraman, Ramprasad; Palekar, Udatta S; Kale, Laxmikant V.

2013. 266-275 Paper presented at 20th Annual International Conference on High Performance Computing, HiPC 2013, Bangalore, India.

Research output: Contribution to conferencePaper

Langer, A, Venkataraman, R, Palekar, US & Kale, LV 2013, 'Parallel branch-and-bound for two-stage stochastic integer optimization', Paper presented at 20th Annual International Conference on High Performance Computing, HiPC 2013, Bangalore, India, 12/18/13 - 12/21/13 pp. 266-275. https://doi.org/10.1109/HiPC.2013.6799130
Langer A, Venkataraman R, Palekar US, Kale LV. Parallel branch-and-bound for two-stage stochastic integer optimization. 2013. Paper presented at 20th Annual International Conference on High Performance Computing, HiPC 2013, Bangalore, India. https://doi.org/10.1109/HiPC.2013.6799130
Langer, Akhil ; Venkataraman, Ramprasad ; Palekar, Udatta S ; Kale, Laxmikant V. / Parallel branch-and-bound for two-stage stochastic integer optimization. Paper presented at 20th Annual International Conference on High Performance Computing, HiPC 2013, Bangalore, India.10 p.
@conference{4824260d241949e99ed8b161c46c87a5,
title = "Parallel branch-and-bound for two-stage stochastic integer optimization",
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.",
author = "Akhil Langer and Ramprasad Venkataraman and Palekar, {Udatta S} and Kale, {Laxmikant V}",
year = "2013",
month = "1",
day = "1",
doi = "10.1109/HiPC.2013.6799130",
language = "English (US)",
pages = "266--275",
note = "20th Annual International Conference on High Performance Computing, HiPC 2013 ; Conference date: 18-12-2013 Through 21-12-2013",

}

TY - CONF

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

AU - Langer, Akhil

AU - Venkataraman, Ramprasad

AU - Palekar, Udatta S

AU - Kale, Laxmikant V

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84900338705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84900338705&partnerID=8YFLogxK

U2 - 10.1109/HiPC.2013.6799130

DO - 10.1109/HiPC.2013.6799130

M3 - Paper

AN - SCOPUS:84900338705

SP - 266

EP - 275

ER -