The Multidimensional 01 Knapsack Problem


Description:The Multidimensional 01 Knapsack problem is a classified NPhard optimization problem. It can be defined as: Input: Output: 

Statement of the ProblemThe NPhard 0–1 multidimensional knapsack problem is a generalisation of the 01 simple knapsack problem. It consists in selecting a subset of given objects (or items) in such a way that the total profit of the selected objects is maximized while a set of knapsack constraints are satisfied. More formally, the problem can be stated as follows:
Where n is the number of objects, m is the number of dimensions that constraints the knapsack, c_{j} represents the benefit of the object j in the knapsack, x_{j} is a binary variable that indicates if the object j has been stored in the knapsack (x_{j}=1) or remains out (x_{j}=0), b_{i} represents the ith dimension's capacity of the knapsack, and a_{i,j} represents the entries of the knapsack's constraints matrix. This matrix stores the constraint value for each object in each dimension (weight, size, volume, prize,...). So the matrix has a NxM size: n columns and m rows. 

Problem InstancesIn order to define an instance of this problem we need to provide the list of objects, indicating all the constraint parameters of each object. We also have to provide the dimensions of the knapsack which is going to be filled. 

Related Bibliography and Papers


Last Updated: 15/07/03 For any question or suggestion, click here to contact with us. 