Optimization Online


Min max (relative) set-regret combinatorial optimization

Alejandro Crema Crema(alejandro.crema***at***ciens.ucv.ve)

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

Keywords: Minmax regret, Robust Programming, Greedy algorithms, Multiparametric Programming

Category 1: Robust Optimization

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization

Citation: Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela. Octubre de 2018

Download: [PDF]

Entry Submitted: 10/31/2018
Entry Accepted: 10/31/2018
Entry Last Modified: 10/31/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society