We consider combinatorial optimization problems with uncertainty in the cost vector. Recently a novel approach was developed to deal such uncertainties: instead of a single one robust solution, obtained by solving a min max problem, the authors consider a set of solutions obtained by solving a min max min problem. In this new approach the set of solutions is computed once and we can choose the best one in real time each time a cost vector occurs yielding better solutions compared to the min max approach. In this paper we extend the new approach by considering the absolute and relative deviation from the optimal values. Algorithms to solve the new min max (relative) set-regret problems are presented with a computational experience.
Citation
Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela. Octubre de 2018