KNAPSACK_MULTIPLE
Data for the 01 Multiple Knapsack Problem

KNAPSACK_MULTIPLE is a dataset directory which contains some examples of data for 01 Multiple Knapsack problems.

In the 01 Multiple Knapsack problem, we are given M knapsacks of capacities C(1:M). We are also given a list of N objects, of weight W(1:N) and profit P(1:N). Our goal is to select objects which can fit into the knapsacks in such a way that we maximize the value of the selected items.

In other words, we are to determine an MxN selection matrix X, whose entries are 0 or 1, such that there is at most a single 1 in any row. X represents our selections, and it must be the case that

        sum ( I ) X(I,J) * W(J) <= C(J)  for each J
      

        sum ( I ) sum ( J ) X(I,J) * P(J)
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

BIN_PACKING, a dataset directory which contains examples of the bin packing problem, in which a number of objects are to be packed in the minimum possible number of uniform bins;

CHANGE_MAKING, a dataset directory which contains test data for the change making problem;

GENERALIZED_ASSIGNMENT, a dataset directory which contains test data for the generalized assignment problem;

KNAPSACK a FORTRAN77 library which solves a variety of knapsack problems.

KNAPSACK_01, a dataset directory which contains test data for the 01 knapsack problem;

LAU_NP, a FORTRAN90 library which implements heuristic algorithms for various NP-hard combinatorial problems.

SUBSET_SUM, a dataset directory which contains examples of the subset sum problem, in which a set of numbers is given, and is desired to find at least one subset that sums to a given target value.

Datasets:

P01 is a set of 10 weights and profits for 2 knapsacks of capacity 70 and 127. Problems 1, 2, 3 and 4 use the same set of weights and profits.

• p01_c.txt, the knapsack capacity.
• p01_w.txt, the weights of the objects.
• p01_p.txt, the profits of each object.
• p01_s.txt, the optimal selection of weights.

P02 is a set of 10 weights and profits for 3 knapsacks of capacity 50, 81, 120. Problems 1, 2, 3 and 4 use the same set of weights and profits.

• p02_c.txt, the knapsack capacity.
• p02_w.txt, the weights of the objects.
• p02_p.txt, the profits of each object.
• p02_s.txt, the optimal selection of weights (not available).

P03 is a set of 10 weights and profits for 4 knapsacks 31, 37, 48, 152. Problems 1, 2, 3 and 4 use the same set of weights and profits.

• p03_c.txt, the knapsack capacity.
• p03_w.txt, the weights of the objects.
• p03_p.txt, the profits of each object.
• p03_s.txt, the optimal selection of weights (not available).

P04 is a set of 10 weights and profits for 1 knapsack of capacity 165. Problems 1, 2, 3 and 4 use the same set of weights and profits.

• p04_c.txt, the knapsack capacity.
• p04_w.txt, the weights of the objects.
• p04_p.txt, the profits of each object.
• p04_s.txt, the optimal selection of weights (not available).

P05 is a set of 6 weights and profits for 2 knapsack of capacity 65 and 85.

• p05_c.txt, the knapsack capacity.
• p05_w.txt, the weights of the objects.
• p05_p.txt, the profits of each object.
• p05_s.txt, the optimal selection of weights.

P06 is a set of 10 weights and profits for 2 knapsack of capacity 103 and 156.

• p06_c.txt, the knapsack capacity.
• p06_w.txt, the weights of the objects.
• p06_p.txt, the profits of each object.
• p06_s.txt, the optimal selection of weights.

You can go up one level to the DATASETS directory.