Is this some variant of the Knapsack Problem?

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.

• Please add some background about why you are interested in this problem. – Kaveh Apr 21 '15 at 5:34
• To me it looks more like a generalization of multicut than knapsack. – Sasho Nikolov Apr 21 '15 at 6:36
• @SashoNikolov You are right, looks more like multicut but the "have to be together" is a constraint. – Nikhil Apr 21 '15 at 14:20
• Google "Quadratic Knapsack Problem". It is not the exact same problem as yours, but it is similar in some features. – ASDF Apr 21 '15 at 18:17
• @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 Apr 22 '15 at 9:57