Robust Optimization for Combinatorial Optimization Problems

Many combinatorial optimization problems arising in real-world applications do not have accurate estimates of the problem parameters when the optimization decision is taken. Stochastic programming and robust optimization are two common approaches for the solution of optimization problems under uncertainty. In this paper, we describe the common definitions of uncertainty set, as well as 3 criteria, min-max, min-max regret and min-max relative regret, to evaluate a solution. Furthermore, we present general lemmas for obtaining worst case scenarios based on a given solution