Optimization Online


Multistage Robust Mixed Integer Optimization with Adaptive Partitions

Dimitris Bertsimas (dbertsim***at***mit.edu)
Iain Dunning (idunning***at***mit.edu)

Abstract: 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.

Keywords: robust optimization, adaptive optimization

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 11/22/2014
Entry Accepted: 11/23/2014
Entry Last Modified: 08/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society