Groupe d’études et de recherche en analyse des décisions

A Robust Approach to Solve Mixed Integer Linear Optimization Problems with Uncertain Data

Marie-Christine Costa ENSTA ParisTech, France

The ever growing performances of mathematical programming solvers allows to be thinking of solving more and more complex problems, and in particular, optimization problems with uncertain data. Here we suppose that the decision-maker makes decisions in two stages: first before discovering the actual value taken by the data, second once uncertainty has been revealed. This second part is called the recourse problem. Two-stage stochastic linear programming is often used in this case but it requires knowing the underlying probability distribution of the data, which is not available in many cases. We present a robust approach that relies only on mild assumptions on the uncertainties involved in the problem, as bounds or reference values of the uncertain data. It looks for a solution that remains satisfactory for all realizations of the data, i.e. for worst scenarios. We first study a general theoretical model with mixed integer decision variables and continuous recourse variables. Then we show that the approach can be generalized, even when the full recourse property is not verified, that is when the problem can have no solution for some values of the first stage decision variables. We finally present two applications: the design of a hybrid energy park for which the recourse variables are continuous, and the design of a telecommunication optical network for which the recourse variables are integer.