How to solve this variant of the Multiple Knapsack problem in which the profits in the objective function is a 2D matrix?

Question

I am looking for ways to solve a variant of the Multiple Knapsack Problem (MKP). I am using Wikipedias definition of the MKP available here: https://en.wikipedia.org/wiki/List_of_knapsack_problems.

I call it the Freelance Treasure Hunter Knapsack Problem (FTHKP) since I cannot seem to fit it in within the other Knapsack or Knapsack-like problems.

The problem goes as follows:

Imagine a treasure hunter stumpling upon n treasures with respective weights w_j in an abandoned ruin. The treasure hunter has m knapsacks, one for each museum the treasure hunter does freelance for. Each knapsack can carry at most weight W_i. Since different museums are interested in different treasures there is a price p_i,j associated with putting treasure number j in knapsack number i. Once sealed by the treasure hunter the knapsacks can only be be opened by their respective museum curators, which means the sorting has to be done on-site. How should the treasure hunter choose which items go in which knapsack in order to maximize profit?

I realize that the problem is a bit contrived, but I wanted to stick to the Knapsack-theme :P.

Anyway, here is the formal definition of the problem:

$$\text{maximize}\sum_{i=1}^m\sum_{j=1}^np_{i,j}x_{i,j}$$ $$\text{subject to:}$$ $$\sum_{j=1}^nw_jx_{i,j}\leq W_i,\text{ }\forall i\in\{1,2,...,m\}$$ $$\sum_{i=1}^mx_{i,j}\leq 1,\text{ }\forall j\in\{1,2,...,n\}$$ $$x_{i,j}\in\{0,1\}$$

If the FTHKP already has a name or is a variant of a more general problem I would like to know what it is. If a full solution is too much of a hassle I appreciate any reading tip on the subject.

Thanks for your time!

Answer 1

So far, your problem constraints are exactly the ones of the multiple knapsack problem. The only thing that changes is your cost function. The multiple knapsack is the particular case of FTHKP where all museums consider items to have the same value. This means that

• You can use any valid inequality or facet ever found for the multiple knapsack, it will be valid for your problem. I recommend this, since a lot of people have been looking for valid inequalities, separation algorithms (and so on) that would be efficient for the MKP.

• The multiple knapsack Your problem is at least as hard as the MKP (complexity, approximability, ...). Any complexity result ever found for the MKP of the kind "MKP cannot ..." is also true for your problem.

On a sidenote, some people call MKP what you call FTHKP (unlike in the wikipedia definition, their cost function is like your, depends on both indices).

You are not exactly in uncharted waters, enjoy it.

Answer 2

The above problem is well known as Generalized Assignment Problem (GAP). You can refer to the following paper 'A PTAS for the Multiple Knapsack Problem' by Chandra Chekuri.