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 {o₁,...o_n}.
-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, 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 i-th 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 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