<p>We are a set of items $I = \{I_1, I_2,.. I_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but certain pairs of items $N = \{(I_i,I_j),..\}$ cannot be together in a knapsack, certain pairs of items $Y = \{(I_i,I_j),..\}$ have to be placed together and for certain pairs there is a cost of not placing them together in a knapsack given by $M = \{(I_i,I_j, C_{ij}),..\}$. The objective is to place all the items in knapsacks such that the constraints specified by $Y$ and $N$ are satisfied and the sum of the overall cost incurred due to not placing items together (given by $M$) is minimised.   </p>

CC BY-SA 3.0
2015-04-21T05:34:05.920Z
Please add some background about why you are interested in this problem.
Kaveh
CC BY-SA 3.0
2015-04-21T06:36:02.957Z
To me it looks more like a generalization of multicut than knapsack.
Sasho Nikolov
CC BY-SA 3.0
2015-04-21T14:20:08.147Z
@SashoNikolov You are right, looks more like multicut but the "have to be together" is a constraint.
Nikhil
CC BY-SA 3.0
2015-04-21T18:17:50.840Z
Google "Quadratic Knapsack Problem". It is not the exact same problem as yours, but it is similar in some features.
ASDF
CC BY-SA 3.0
2015-04-22T09:57:36.507Z
@SashoNikolov If we collapse all items that have to be together as a single item, and then solve the multicut then both the sets of constraints (must be together and must not be together) get satisfied. Is this what you are saying?
Nikhil
<complexity-classes><reductions>
Is this some variant of the Knapsack Problem?
Nikhil
# Is this some variant of the Knapsack Problem?

(Asked by: username_0 on 2015-04-21)

We are a set of items $I = \{I\_1, I\_2,.. I\_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but certain pairs of items $N = \{(I\_i,I\_j),..\}$ cannot be together in a knapsack, certain pairs of items $Y = \{(I\_i,I\_j),..\}$ have to be placed together and for certain pairs there is a cost of not placing them together in a knapsack given by $M = \{(I\_i,I\_j, C\_{ij}),..\}$. The objective is to place all the items in knapsacks such that the constraints specified by $Y$ and $N$ are satisfied and the sum of the overall cost incurred due to not placing items together (given by $M$) is minimised.

**Tags:** complexity-classes, reductions
> **Comments:**
> **username_1**: Please add some background about why you are interested in this problem.  
> **username_2**: To me it looks more like a generalization of multicut than knapsack.  
> **username_0**: @SashoNikolov You are right, looks more like multicut but the "have to be together" is a constraint.  
> **username_3**: Google "Quadratic Knapsack Problem". It is not the exact same problem as yours, but it is similar in some features.  
> **username_0**: @SashoNikolov If we collapse all items that have to be together as a single item, and then solve the multicut then both the sets of constraints (must be together and must not be together) get satisfied. Is this what you are saying?  

---

## 0 answers

