4
$\begingroup$

I'm working on a problem which MAY be reduced to the following version of Knapsack:

Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in the knapsack, then for some $i$ and $j$, the combined profit of $e_i$ and $e_j$ is NOT $p_i+p_j$. It could be lower or higher. Note that in general, profits could be additive, but for some pairs of elements, our new rule holds, and we know in advance the value of $profit(\{e_i\} \cup \{e_j\})$ for such pairs. As always we want to maximize total profit.

So my question is, has work been done on such a variant of knapsack? Are there papers that can I read to better understand this formulation? I am not well-versed with the entire literature of Knapsack, and I tried to search for this but came up empty.

Improve this question
$\endgroup$
4
  • $\begingroup$ Dynamic programming would still work, wouldn't it? $\endgroup$
    – elexhobby
    Mar 8, 2014 at 22:57
  • $\begingroup$ there are two cases when adding e_j: a) e_i was already in the solution, then you have to check whether the weight increases or decreases. b) e_i was not in the solution, so now you have to check whether adding e_i is worth it, keeping in mind what elements you will be displacing. $\endgroup$
    – Ali
    Mar 8, 2014 at 23:03
  • 14
    $\begingroup$ I don't think the objective function is precisely described. What exactly is the profit of a subset of given items? $\endgroup$
    – Chandra Chekuri
    Mar 9, 2014 at 2:36
  • 1
    $\begingroup$ I just found out that what I was looking for is the Quadratic Knapsack problem. $\endgroup$
    – Ali
    Mar 21, 2014 at 21:00

1 Answer 1

Reset to default
0
$\begingroup$

This is a very interesting problem. But cannot be addressed in its general form. Assumptions need to be made in relation to the application domain. You may find the attached paper useful. The paper assumes strengths of value-related dependencies are imprecise.

please see this: https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12

Improve this answer
$\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.