The Multidimensional 0-1 Knapsack Problem



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

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

-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:

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

Computers and Intractability: A Guide to the Theory of Np-Completeness
by Michael R. Garey, David S. Johnson
How to Solve It: Modern Heuristics
by Zbigniew Michalewicz, David B. Fogel
Parallel Skeletons for Tabu Search Method Based on Search Strategies and Neighborhood Partition
by M.J. Blesa, Ll. Hernàndez, F. Xhafa
Parallel Skeletons for Tabu Search Method
by M.J. Blesa, Ll. Hernàndez, F. Xhafa
Tabu search for 0-1 multidimensional knapsack revisited: choosing internal heuristicsand fine tuning of parameters
by M.J. Blesa, Ll. Hernàndez, F. Xhafa
A compendium of NP optimization problems
Experiments for the 0-1 Multidimensional Knapsack Problem. MALLBA Project

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