Overview
Knapsack Sharing Problem (KSP) is one of the challenging problems in Operations Research (OR) area. A KSP instance is defined with a set of n items, a single shared knapsack with a positive capacity c. In addition, the set of the n items is divided into m disjoint classes
with different cardinalities. Let the set of all items be N = {1...n}, the set of all classes be M = {1...m}, and the set of items within the i th class be N_i = {1...n_i } for i ∈ M where n_i is the cardinality of the i^th class. Each item is characterized with a positive profit p_ij and a positive weight w_ij where i is the class index and j is the item index within the i th class (j th item in the i th class). The KSP is a max-min problem where the objective is to assign a subset of items to the shared knapsack so that the class with the minimum profit should be maximized under the knapsack capacity constraint.
In this page, we provide some randomly generated data-sets that we have used to assess the performance of the proposed Sharknap
exact algorithm to solve the KSP problem. These data-sets are divided into four groups where each group corresponds to one type of instance namely :
Uncorrelated, Weakly correlated, Strongly correlated, and Multiple Subset-sum instances. These data-sets are of a medium size in which the number
of items n ranges between 20000 and 50000.