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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.