A Generalized Minimax Regret Approach for Optimization Problems under Severe Uncertainty with Linear Objectives

In this paper, 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.