<p>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:</p>
<p><a href="https://etheses.bham.ac.uk/id/eprint/7532/2/Joshi17PhD.pdf" rel="nofollow noreferrer">https://etheses.bham.ac.uk/id/eprint/7532/2/Joshi17PhD.pdf</a></p>

CC BY-SA 4.0
2021-01-22T12:18:02.440Z
2021-01-22T12:18:02.440Z
Lukas
<p>I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:</p>
<p>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.</p>
<p>For example, suppose two items <span class="math-container">$a$</span> and <span class="math-container">$b$</span> have profit <span class="math-container">$p_{ai}$</span> and <span class="math-container">$p_{bi}$</span> and weight <span class="math-container">$w_{ai}$</span> and <span class="math-container">$w_{bi}$</span> in the <span class="math-container">$i^{th}$</span>knapsack. If the item <span class="math-container">$a$</span> is selected to the knapsack <strong><span class="math-container">$i$</span></strong>, everything goes well. However, if both items are presented to knapsack <strong><span class="math-container">$i$</span></strong>, the combined profit of <span class="math-container">$a$</span> and <span class="math-container">$b$</span> is not <span class="math-container">$p_{ai} + p_{bi}$</span> and instead be little smaller than that. The total weight of <span class="math-container">$a$</span> and <span class="math-container">$b$</span> is also larger than <span class="math-container">$w_{ai} + w_{bi}$</span>. 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 <span class="math-container">$a$</span>, <span class="math-container">$b$</span> and <span class="math-container">$c$</span>, its profit is not <span class="math-container">$p_{ai} + p_{bi} + p_{ci}$</span> or <span class="math-container">$Value({a, b}) + Value({a, c}) + Value({b, c})$</span> and its weight is not <span class="math-container">$w_{ai}+w_{bi} + w_{ci}$</span>. 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.</p>
<p>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.</p>

<ds.algorithms><optimization>
Knapsack problem with dependent weight and profits among the items
Yukinari
# Knapsack problem with dependent weight and profits among the items

(Asked by: username_0 on 2021-01-21)

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.

**Tags:** ds.algorithms, optimization


---

## 1 answers

### Answer by username_1 on 2021-01-22. Score: 1

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>


---

