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 wj 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
Wi. Since
different museums are interested in different treasures there is a price
pi,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!
Best Answer
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.