2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! It's feels good to know that it is similar to the MKP in terms of complexity and approximability since I have a heuristic approach to the problem. $\endgroup$ – Zluudg Mar 22 '17 at 14:55
  • $\begingroup$ @Zluudg at least as hard, not similar. There are many complexity classes (check out the complexity zoo), and the fthkp may be different with some classes $\endgroup$ – Vincent Mar 22 '17 at 14:58
  • $\begingroup$ Ok, I'll check it out. Seems like a fun website, thanks :) $\endgroup$ – Zluudg Mar 22 '17 at 15:37
  • $\begingroup$ @Vincent, Are you aware of greedy algorithms for this variant - math.stackexchange.com/questions/2415617? Thank You. $\endgroup$ – Royi Sep 4 '17 at 7:15
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.