Poster: enabling massive parallelism for stochastic optimization

The US air fleet 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. Airfleet management involves periodically allocating aircraft to its myriad operations, while judiciously accounting 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 approach with two-stage linear programs. This allows the evaluation of tens of thousands of possible scenarios while converging to an optimal integer allocation for extremely large problems. We believe that this is an interesting and uncommon approach to harnessing tera/petascale compute power for such problems without decomposing the linear programs further.