The lexicographic α-robust knapsack problem

Abstract : The knapsack problem is a classical combinatorial optimization problem used to model many industrial situations. The robust version of this problem was studied in the literature using a max-min or min-max regret criterion. In this paper, we show the drawbacks of such criteria and propose a new robustness approach, called lexicographic α-robustness. We show that the complexity of the lexicographic α-robust problem does not increase compared with the max-min version and present a pseudo-polynomial algorithm in the case of a bounded number of scenarios.
Type de document :
Article dans une revue
International Transactions in Operational Research, Wiley, 2011, Vol. 18 (n° 1), pp 103-113. 〈10.1111/j.1475-3995.2010.00786.x〉
Liste complète des métadonnées

https://hal-rbs.archives-ouvertes.fr/hal-00820135
Contributeur : Sandrine Palmer <>
Soumis le : vendredi 3 mai 2013 - 11:31:52
Dernière modification le : jeudi 11 janvier 2018 - 06:17:30

Lien texte intégral

Identifiants

Collections

PSL

Citation

Rim Kalaï, Daniel Vanderpooten. The lexicographic α-robust knapsack problem. International Transactions in Operational Research, Wiley, 2011, Vol. 18 (n° 1), pp 103-113. 〈10.1111/j.1475-3995.2010.00786.x〉. 〈hal-00820135〉

Partager

Métriques

Consultations de la notice

253