Multistage Robust Mixed-Integer Optimization with Adaptive Partitions

Dimitris Bertsimas () and Iain Dunning ()
Additional contact information
Dimitris Bertsimas: Operations Research Center and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Iain Dunning: Operations Research Center and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2016, vol. 64, issue 4, 980-998

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 (nonadaptive) 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 its convergence properties and the growth in the number of partitions. Using these 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 nonadaptive 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 the number of time stages and the number of decision variables.

Keywords: adaptive optimization; robust optimization; integer optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1515 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:4:p:980-998

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().