The lexicographic α-robust knapsack problem
Kalaï, Rim; Vanderpooten, Daniel (2011), The lexicographic α-robust knapsack problem, International Transactions in Operational Research, 18, 1, p. 103-113. http://dx.doi.org/10.1111/j.1475-3995.2010.00786.x
TypeArticle accepté pour publication ou publié
Journal nameInternational Transactions in Operational Research
MetadataShow full item record
Abstract (EN)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.
Subjects / Keywordsuncertainty; robustness; 0–1 knapsack problem; min–max (regret); complexity
Showing items related by title and author.
Kalaï, Rim; Aloulou, Mohamed Ali; Vallin, Philippe; Vanderpooten, Daniel (Université Paris-DauphineParis, 2006) Document de travail / Working paper