Eggenberg, N., Salani, M., and Bierlaire, M. (2009)

UFO: Uncertainty Feature Optimization, an Implicit Paradigm for Problems with Noisy Data

Optimization problems due to noisy data solved using stochastic programming or robust optimization approaches require the explicit characterization of an uncertainty set U that models the nature of the noise. Such approaches depend on the modeling of the uncertainty set and suffer from an erroneous estimation of the noise. In this paper, we introduce a framework that considers the uncertain data implicitly. We define the concept of Uncertainty Features (UF), which are problem-specific structural properties of a solution. We show how to formulate an uncertain problem using the Uncertainty Feature Optimization (UFO) framework as a multi-objective problem. We show that stochastic programming and robust optimization are particular cases of the UFO framework. We present computational results for the Multi-Dimensional Knapsack Problem (MDKP) and discuss the application of the framework to the airline scheduling problem.