# The Multidimensional 0-1 Knapsack Problem ## Description:

The Multidimensional 0-1 Knapsack problem is a classified NP-hard optimization problem. It can be defined as:

Input:
-A set O of objects {o1,...on}.
-A knapsack K.

Output:
-A set O' of objects stored on the knapsack. ## Statement of the Problem

The NP-hard 0–1 multidimensional knapsack problem is a generalisation of the 0-1 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:

 Maximizes subject to  Where n is the number of objects, m is the number of dimensions that constraints the knapsack, cj represents the benefit of the object j in the knapsack, xj is a binary variable that indicates if the object j has been stored in the knapsack (xj=1) or remains out (xj=0), bi represents the i-th dimension's capacity of the knapsack, and ai,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 Instances

In 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

 TextBook Computers and Intractability: A Guide to the Theory of Np-Completeness by Michael R. Garey, David S. Johnson TextBook How to Solve It: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel TextBook Parallel Skeletons for Tabu Search Method Based on Search Strategies and Neighborhood Partition by M.J. Blesa, Ll. Hernàndez, F. Xhafa TextBook Parallel Skeletons for Tabu Search Method by M.J. Blesa, Ll. Hernàndez, F. Xhafa TextBook Tabu search for 0-1 multidimensional knapsack revisited: choosing internal heuristicsand fine tuning of parameters by M.J. Blesa, Ll. Hernàndez, F. Xhafa URL A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html URL Experiments for the 0-1 Multidimensional Knapsack Problem. MALLBA Project http://www.lsi.upc.es/~mallba/public/library/TabuSearch/01mknp.html Last Updated: 15/07/03                                                                                                                  For any question or suggestion, click here to contact with us.