Absolute regret of implicitly defined sets for combinatorial optimization problems

A Crema(alejandrocremagmail.com)

Abstract: 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.

Keywords: Robustness and sensitivity analysis, Combinatorial optimization, Mixed integer programming, Min max min absolute regret.

Category 1: Robust Optimization

Citation: Facultad de Ciencias, Universidad Central de Venezuela

Download: [PDF]

Entry Submitted: 01/01/2022
Entry Accepted: 01/01/2022
Entry Last Modified: 01/01/2022

Modify/Update this entry