The lexicographic α-robust knapsack problem

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.ou