Enabling massive parallelism for stochastic optimization problems

Akhil Langer, Ramprasad Venkataraman, Gagan Gupta, Laxmikant Kale, Udatta Palekar, Steven Baker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The US air eet is tasked with the worldwide movement of cargo and personnel. Due to a unique mixture of operating circumstances, it faces a large scale and dynamic set of cargo movement demands with sudden changes almost being the norm. Aireet management involves periodically allocating aircraft to its myriad operations, while judiciously account-ing for this uncertainty to minimize operating costs. We have formulated this allocation problem as the optimization of a stochastic two-stage integer program. Our work aims to enable rapid decisions via a scalable parallel implementation. We present our initial attempts at parallelization and eventually, a branch-and-bound ap-proach with two-stage linear programs. This allows the eval-uation of tens of thousands of possible scenarios while con-verging to an optimal integer allocation for extremely large problems. We believe that this is an interesting and uncom-mon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.

Original languageEnglish (US)
Title of host publicationSC'11 - Proceedings of the 2011 High Performance Computing Networking, Storage and Analysis Companion, Co-located with SC'11
Pages89-90
Number of pages2
DOIs
StatePublished - Dec 1 2011
Event2011 High Performance Computing Networking, Storage and Analysis, SC'11, Co-located with SC'11 - Seattle, WA, United States
Duration: Nov 12 2011Nov 18 2011

Publication series

NameSC'11 - Proceedings of the 2011 High Performance Computing Networking, Storage and Analysis Companion, Co-located with SC'11

Other

Other2011 High Performance Computing Networking, Storage and Analysis, SC'11, Co-located with SC'11
CountryUnited States
CitySeattle, WA
Period11/12/1111/18/11

Keywords

  • Aireet Management
  • Parallel Branch and Bound
  • Simu-lation
  • Stochastic optimization

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Enabling massive parallelism for stochastic optimization problems'. Together they form a unique fingerprint.

Cite this