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.
