Random Knapsack Problems Datasets

2013-07-30

In my recent "Intensive Genetic Algorithms" course, I asked the students to implement a GA for two different formulations of the Knapsack problem.

I dug through the internet for a few data sets (here and here). But it would be nice to also have a way to generate more random sets of variable size.

(Of course, since the challenge is to implement the GA that solves a generic Knapsack problem, I could just create large "interesting" data sets simply by removing constraints such as "the data set needs to have one optimal solution" - but how fun is that?)

Surprisingly, a google search for "Knapsack Random Data sets" and "Generating Knapsack Data Sets" didn't turn out much. This paper (from 1979!) mentions using randomly generated data, but does not explain how the data was generated. This other mentions using different distributions to sample the weights and profits of the knapsack pieces, but it seems that no effort is made to guarantee the existence of a single optimal solution, or a particular distribution of solutions (as opposed to a distribution of pieces).

Maybe it is not a very important problem, but it sure got my attention for a brief moment.


Click here to read older entries!