variation on generalized assignment

Question

I'm looking to solve a constrained optimization problem. I believe it is a variant of the generalized assignment problem.

I have n kinds of items, x₁ through x_n and m kinds of bins b₁ through b_m. There is an overall budget w. For a bin b_i, each item x_j has a profit p_ij and a weight w_ij. We want to:

find x_ij, which indicates the number of items of type j in bin i
maximize sum(i=1 to m) sum(j=1 to n) p_ij x_ij
subject to:
sum(i=1 to m) sum(j=1 to n) w_ij x_ij <= w (total weight budget)
sum(i=1 to m) x_ij <= 1 (each item goes in 0 or 1 bins)
each x_ij is equal to 0 or 1 (no partial or negative item assignments)

So this is identical to the generalized assignment problem as presented on Wikipedia, but there is an overall budget instead of a budget for each bin.

I'm wondering whether this maps to another named problem so I can read about known solutions.

Answer 1

This is variation of 0-1 knapsack problem with mn items.

We can view different weights and profits in bins as different items. We have mn items x₁₁ ... x_mn, where item x_ij have weight w_ij and profit p_ij. The only difference from knapsack problem is that we can take at most one item from one "group" of items (items with same type). But regarding dynamic programming algorithm, this is simplification, because you don't need to take combinations of items in one group into account.