Multidimensional Knapsack Problem Based on Uncertain Measure

Abstract

The research of classical multidimensional knapsack problem always assumes that the weights,the values and the capacities are constant values. However, in the real-life industrial engineering applica-tions, the multidimensional knapsack problem often comes with uncertainty for lacking of the informationabout these parameters. This paper investigates a constrained multidimensional knapsack problem underuncertain environment, in which the relevant parameters are assumed to be uncertain variables. Withinthe framework of uncertainty theory, two types of uncertain programming models with discount con-straints are constructed for the problem with di erent decision criteria, i.e., the expected value criterionand the critical value criterion. Taking full advantage of the operational law for uncertain variables, theproposed models can be transformed into their corresponding deterministic models. After theoreticallyinvestigating the properties of the models, we do some numerical experiments. The numerical resultsillustrate that the proposed models are feasible and e cient for solving the constrained multidimensionalknapsack problem with uncertain parameters.