GENERALIZED_ASSIGMENT
Data for the Generalized Assignment Problem

GENERALIZED_ASSIGMENT is a dataset directory which contains some examples of data for Generalized Assignment problems.

In the Generalized Assignment problem, we are given M knapsacks of capacities C(1:M). We are also given a list of N objects, with corresponding weights and profits. However, the weight and profit of an object now depend on the knapsack to which it is defined, so we have MxN arrays W and P. Our goal is to assign each object to exactly one knapsack so that no knapsack's capacity is exceeded, and the total profit is maximized.

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

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

        sum ( I ) sum ( J ) X(I,J) * P(I,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;

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;

KNAPSACK_MULTIPLE, a dataset directory which contains test data for the multiple 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 7 objects and 2 knapsacks.

• p01_c.txt, the knapsack capacities.
• p01_w.txt, the weights of the objects.
• p01_p.txt, the profits of each object.
• p01_s.txt, the optimal selection of each weight to a knapsack (not available)

P02 is a set of 5 weights and 2 knapsacks.

• 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 each weight to a knapsack (not available).

P03 is a set of 8 weights and 3 knapsacks.

• 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, a optimal assignment of each weight to a knapsack.

You can go up one level to the DATASETS directory.