Enabling massive parallelism for stochastic optimization problems

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.