Performance optimization of a parallel, two stage stochastic linear program

Akhil Langer, Ramprasad Venkataraman, Udatta S Palekar, Laxmikant V Kale, Steven Baker

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

Abstract

Stochastic optimization is used in several high impact contexts to provide optimal solutions in the face of uncertainties. This paper explores the parallelization of two-stage stochastic resource allocation problems that seek an optimal solution in the first stage, while accounting for sudden changes in resource requirements by evaluating multiple possible scenarios in the second stage. Unlike typical scientific computing algorithms, linear programs (which are the individual grains of computation in our parallel design) have unpredictable and long execution times. This confounds both a priori load distribution as well as persistence-based dynamic load balancing techniques. We present a master-worker decomposition coupled with a pull-based work assignment scheme for load balance. We discuss some of the challenges encountered in optimizing both the master and the worker portions of the computations, and techniques to address them. Of note are cut retirement schemes for balancing memory requirements with duplicated worker computation, and scenario clustering for accelerating the evaluation of similar scenarios. We base our work in the context of a real application: the optimization of US military aircraft allocation to various cargo and personnel movement missions in the face of uncertain demands. We demonstrate scaling up to 122 cores of an intel® 64 cluster; even for very small, but representative datasets. Our decision to eschew problem-specific decompositions has resulted in a parallel infrastructure that should be easily adapted to other similar problems. Similarly, we believe the techniques developed in this paper will be generally applicable to other contexts that require quick solutions to stochastic optimization problems.

Original languageEnglish (US)
Title of host publicationProceedings of the 2012 IEEE 18th International Conference on Parallel and Distributed Systems, ICPADS 2012
Pages676-683
Number of pages8
DOIs
StatePublished - Dec 1 2012
Event18th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2012 - Singapore, Singapore
Duration: Dec 17 2012Dec 19 2012

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN (Print)1521-9097

Other

Other18th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2012
CountrySingapore
CitySingapore
Period12/17/1212/19/12

Keywords

  • Airfleet management
  • Large scale optimization
  • Parallel computing
  • Stochastic optimization

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Performance optimization of a parallel, two stage stochastic linear program'. Together they form a unique fingerprint.

Cite this