Optimization Under Severe Uncertainty: a Generalized Minimax Regret Approach for Problems with Linear Objectives

We study a general optimization problem with an uncertain linear objective. We address the uncertainty using two models: belief functions and, more generally, capacities. In the former model, we use the generalized minimax regret criterion introduced by Yager, while in the latter one, we extend this criterion, to find optimal solutions. This paper identifies some tractable cases for the resulting problem. Furthermore, when focal sets of the considered belief functions are Cartesian products of intervals, we develop a 2-approximation method that mirrors the well-known midpoint scenario method used for minimax regret optimization problems with interval data.