BIN_PACKING
Data for the Bin Packing Problem

BIN_PACKING is a dataset directory which contains some examples of data for the bin packing problems.

In the bin packing problem, we are given a set of N objects, of a variety of weights W(I). We have an unlimited supply of bins, each of capacity C. Our goal is to assign each object to a bin in such a way that we do not exceed the capacity of any bin, while using the fewest number of bins possible.

Thus, a solution of the bin packing problem is an assignment vector S of length N which indicates which bin each object goes to, and the "cost" of the solution is the maximum bin index.

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:

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 0/1 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.

PARTITION_PROBLEM, a dataset directory which contains examples of the partition problem, in which a set of numbers is given, and it is desired to break the set into two subsets with equal sum.

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 9 objects for bins of capacity 100.

• p01_c.txt, the bin capacity.
• p01_w.txt, the weights of the objects.
• p01_s.txt, the optimal assignment of weights.

P02 is a set of 14 objects for bins of capacity 100.

• p02_c.txt, the bin capacity.
• p02_w.txt, the weights of the objects.
• p02_s.txt, the optimal assignment of weights.

P03 is a set of 10 objects for bins of capacity 100.

• p03_c.txt, the bin capacity.
• p03_w.txt, the weights of the objects.
• p03_s.txt, an assignment of weights using 4 bins. It is possible to do better.

P04 is a set of 33 objects for bins of capacity 524. If the strategy of first-fit, heaviest-to-lightest is used, then 7 bins are needed. However, if the 46 pound weight is removed from this list, the same strategy ends up using 8 bins! This example is due to Ronald Graham.

• p04_c.txt, the bin capacity.
• p04_w.txt, the weights of the objects.
• p04_s.txt, an assignment of weights using 7 bins.

You can go up one level to the DATASETS directory.