Live Webcast 15th Annual Charm++ Workshop

Many real-world planning problems require searching for an optimal solution in the face of uncertain input. One approach to is to express them as a two-stage stochastic optimization problem where the search for an optimum in one stage is informed by the evaluation of multiple possible scenarios in the other stage. If integer solutions are required, then branch-and-bound techniques are the accepted norm. However, there has been little prior work in parallelizing and scaling branch-and-bound algorithms for such problems. In this paper, we explore the parallelization of a two-stage stochastic integer program solved using branch-and-bound. We present three design variations and describe the factors that shaped our quest for scalability. Our designs seek to increase the exposed parallelism while delegating sequential linear program solves to existing libraries. We evaluate the scalability of our designs using sample aircraft allocation problems for the US airfleet. These problems greatly incentivize short times to solution. Unlike typical, iterative scientific applications, we encounter some very interesting characteristics that make it challenging to realize a scalable design. The total amount of computation required to find optima is not constant across multiple runs. This challenges traditional thinking about scalability and parallel efficiency. It also implies that reducing idle time does not imply quicker runs. The sequential grains of computation are quite coarse. They display a wide variation and unpredictability in sizes. The structure of the branch-and-bound search tree is sensitive to several factors, any of which can significantly alter the search tree causing longer times to solution. We explore the causes for this fragility and evaluate the trade-offs between scalability and repeatability. Our attempts result in strong scaling to hundreds of cores for the small, sample datasets that we use. We believe our experiences will feed usefully into further research on this topic.