We present a new partition-and-bound method for multistage adaptive mixed integer optimization (AMIO) problems that extends previous work on finite adaptability. The approach analyzes the optimal solution to a static (non-adaptive) version of an AMIO problem to gain insight into which regions of the uncertainty set are restricting the objective function value. We use this information to construct partitions in the uncertainty set, leading to a finitely adaptable formulation of the problem. We use the same information to determine a lower bound on the fully adaptive solution. The method repeats this process iteratively to further improve the objective until a desired gap is reached. We provide theoretical motivation for this method, and characterize both its convergence properties and the growth in the number of partitions. Using this insights we propose and evaluate enhancements to the method such as warm starts and smarter partition creation. We describe in detail how to apply finite adaptability to multistage AMIO problems to appropriately address nonanticipativity restrictions. Finally we demonstrate in computational experiments that the method can provide substantial improvements over a non-adaptive solution and existing methods for problems described in the literature. In particular, we find that our method produces high-quality solutions versus the amount of computational effort, even as the problem scales in both number of time stages and in the number of decision variables.
Article
View Multistage Robust Mixed Integer Optimization with Adaptive Partitions