Softening the Robustness of Optimization Problems: A New Budgeted Uncertainty Approach

In this paper an optimization problem with uncertain parameters is discussed. In the traditional robust approach a pessimistic point of view is assumed. Namely, a solution is computed under the worst possible parameter realizations, which can lead to large deterioration of the objective function value. In this paper a new approach is proposed, which assumes a less pessimistic point of view. The complexity of the resulting problem is explored and some methods of solving its special cases are presented.