Technical Note—Multistage Robust Mixed-Integer Programming

Abstract

Multistage robust optimization, in which decisions are taken sequentially as new information becomes available about uncertain problem parameters, is a very versatile yet computationally challenging paradigm for decision making under uncertainty. In this technical note, we propose a new model and solution approach for multistage robust mixed-integer programs, which may contain both continuous and discrete decisions at any time stage. Our model builds upon the finite adaptability scheme developed for two-stage robust optimization problems, and it allows us to decompose the multistage problem into a large number of much simpler two-stage problems. We discuss how these two-stage problems can be solved both exactly and approximately, and we report numerical results for route planning and location-transportation problems.