Robust optimization models with mixed-integer uncertainty sets

Abstract

In many real-world decision-making problems, some parameters are uncertain and decision-makers have to solve optimization models under uncertainty. In this study, we address two specific classes of problems with uncertain parameters and we are interested in solutions that are robust under any realization of uncertainty. The first one is a class of minimum-cost flow problems where the arcs are subject to multiple ripple-effect disruptions that increase their usage cost. The locations of the disruptions' epicenters are uncertain, and the decision-maker seeks a flow that minimizes cost assuming the worst-case realization of the disruptions. We evaluate the damage to each arc using different methods in which the arcs’ costs post-disruptions are represented with a mixed-integer feasible region. In the second class, we propose a novel problem that considers a decision-maker (a government agency or a public-private consortium) who seeks to efficiently allocate resources in retrofitting and recovery strategies to minimize social vulnerability under an uncertain tornado. As tornado paths cannot be forecast reliably, we model the problem using a two-stage robust optimization problem with a mixed-integer nonlinear uncertainty set that represents the tornado damage.

In this study, our primary objective is to develop a mathematical and algorithmic framework for modeling and solving these specific problems. To accomplish this goal, we utilize robust optimization to formulate these problems; develop decomposition algorithms inspired by methods of mixed-integer optimization; and exploit the geometrical characteristics of the uncertainty sets to enhance the formulations and algorithms. We test our proposed approaches over real datasets and synthetic instances. The numerical experiments show that our methods provide sound decision-making strategies under uncertainty and achieve orders of magnitude improvements in computational times over standard approaches from the literature.