We consider combinatorial optimization problems with interval uncertainty in the cost vector. Recently a new approach was developed to deal with such uncertainties: instead of a single one absolute robust solution, obtained by solving a min max problem, a set of cardinality predefined and minimal absolute regret, obtained by solving a min max min problem, is considered. With that approach, the set of solutions is computed once and then 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 that approach by presenting an algorithm to compute the absolute regret of an implicitly defined set and a greedy heuristic to deal with the min max min absolute regret problem for a practical interest case.
Citation
Facultad de Ciencias, Universidad Central de Venezuela
Article
View Absolute regret of implicitly defined sets for combinatorial optimization problems