Min-max and min-max (relative) regret approaches to representatives selection problem

Abstract : The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min-max and min-max (relative) regret approaches are used for making a selection decision. The arising min-max, min-max regret and min-max relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.
Type de document :
Article dans une revue
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2012, Volume 10 (Issue 2), pp 181-192. 〈10.1007/s10288-012-0202-3〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00693479
Contributeur : Florent Breuil <>
Soumis le : mercredi 2 mai 2012 - 17:06:52
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

Citation

Alexandre Dolgui, Sergey Kovalev. Min-max and min-max (relative) regret approaches to representatives selection problem. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2012, Volume 10 (Issue 2), pp 181-192. 〈10.1007/s10288-012-0202-3〉. 〈emse-00693479〉

Partager

Métriques

Consultations de la notice

122