1
$\begingroup$

I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:

Each knapsack has its own valuation function; an item brings different profit and weight to a specific knapsack. Also, the profit and weight of an item depend on the profit and weight that has been assigned to the knapsack.

For example, suppose two items $a$ and $b$ have profit $p_{ai}$ and $p_{bi}$ and weight $w_{ai}$ and $w_{bi}$ in the $i^{th}$knapsack. If the item $a$ is selected to the knapsack $i$, everything goes well. However, if both items are presented to knapsack $i$, the combined profit of $a$ and $b$ is not $p_{ai} + p_{bi}$ and instead be little smaller than that. The total weight of $a$ and $b$ is also larger than $w_{ai} + w_{bi}$. Though, we can know the value of each combination, it takes expensive computation overheads. This relationship is not limited between two items, but holds among all items, which means if a knapsack is assigned three items $a$, $b$ and $c$, its profit is not $p_{ai} + p_{bi} + p_{ci}$ or $Value({a, b}) + Value({a, c}) + Value({b, c})$ and its weight is not $w_{ai}+w_{bi} + w_{ci}$. As usual, we always want to maximize the total profit. Though, it seems like a variant of quadratic knapsack problem, the overhead to compute the additional profit for all subsets is too costly.

My question is, has there work been done on this variant of (multiple)knapsack problem? Are there any papers that I can read to better understand it? I am not very familiar with the literature of knapsack problems and have tried to search for this but still gets little useful.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hi that sounds quite a lot like the multiobjective Knapsack Problem to me. It has undergone some research for example by the bio-inspired computation community, see for example here:

https://etheses.bham.ac.uk/id/eprint/7532/2/Joshi17PhD.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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