SC14 New Orleans, LA

The International Conference for High Performance Computing, Networking, Storage and Analysis

Parallel Algorithms for Two-Stage Stochastic Optimizations.

Student: Akhil Langer (University of Illinois at Urbana-Champaign)
Advisor: Laxmikant V. Kale (University of Illinois at Urbana-Champaign)
Abstract: Many real-world planning problems require searching for an optimal solution in the face of uncertain input. In two-stage stochastic optimization problem, search for an optimum in one stage is informed by the evaluation of multiple possible scenarios in the other stage. Stochastic optimization has applications in production, financial modeling, transportation (road as well as air), supply chain, scheduling, environmental and pollution control, telecommunications and electricity. In this work, 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 evaluate the scalability of our designs and compare its performance with the state-of-the-art integer linear program solvers such as Gurobi. Our attempts result in strong scaling to hundreds of cores for these datasets.

Summary: pdf

Doctoral Showcase Index