Multidimensional Knapsack Problem Based on Uncertain Measure

Document Type : Article


1 College of Mathematics and Physics, Huanggang Normal University, Hubei 438000, China

2 School of Science, Wuhan University of Technology, Wuhan 430070, China

3 College of Mathematics and Sciences, Shanghai Normal University, Shanghai 200234, China


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 information
about these parameters. This paper investigates a constrained multidimensional knapsack problem under
uncertain environment, in which the relevant parameters are assumed to be uncertain variables. Within
the 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 criterion
and the critical value criterion. Taking full advantage of the operational law for uncertain variables, the
proposed models can be transformed into their corresponding deterministic models. After theoretically
investigating the properties of the models, we do some numerical experiments. The numerical results
illustrate that the proposed models are feasible and ecient for solving the constrained multidimensional
knapsack problem with uncertain parameters.


Main Subjects