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 Jwhile we try to maximize our total profit:

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

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

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.

**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.