Multistage Robust Discrete Optimization via Quantified Integer Programming
Preprint
Abstract
Decision making needs to take an uncertain environment into account. Over the last decades, robust optimization has emerged as a preeminent method to produce solutions that are immunized against uncertainty. The main focus in robust discrete optimization has been on the analysis and solution of one- or two-stage problems, where the decision maker has limited options in reacting to additional knowledge gained after parts of the solution have been fixed. Due to its computational difficulty, multistage problems beyond two stages have received less attention. In this paper we argue that multistage robust discrete problems can be seen through the lens of quantified integer programs, where powerful tools to reduce the search tree size have been developed. By formulating both integer and quantified integer programming formulations, it is possible to compare the performance of state-of-the-art solvers from both worlds. Using selection, assignment, lot-sizing and knapsack problems as a testbed, we show that problems with up to nine stages can be solved to optimality in reasonable time.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Multistage adaptive optimization using hybrid scenario and decision rule formulationAIChE Journal, 2019
- A data‐driven multistage adaptive robust optimization framework for planning and scheduling under uncertaintyAIChE Journal, 2017
- Binary decision rules for multistage adaptive mixed-integer optimizationMathematical Programming, 2017
- Robust optimization of uncertain multistage inventory systems with inexact data in decision rulesComputational Management Science, 2016
- Multi‐stage adjustable robust optimization for process scheduling under uncertaintyAIChE Journal, 2016
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004
- Robust discrete optimization and network flowsMathematical Programming, 2003
- Robust optimization ? methodology and applicationsMathematical Programming, 2002
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- Cutting planes for integer programs with general integer variablesMathematical Programming, 1998