3
$\begingroup$

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each having a weight and volume capacity, where these items need to go inside. A feature that I am looking for is that the value property of each item which depends on which knapsack it goes into. For instance, item 1 has value of v1 if goes into knapsack 1, and v2 if it goes to knapsack 2.

How can I model the problem as a knapsack and an optimization problem so to maximize the overall value? So far I came into a multiple knapsack problem, 2 dimensional. For for the value, I don't have any clue.

$\endgroup$
1
$\begingroup$

The simplest approach is to formulate this as an instance of integer lienar programming. You have zero-or-one variables $x_{i,j}$, where $x_{i,j}=1$ means that item $i$ is placed into knapsack $j$. Then all of your constraints can be straightforwardly expressed as linear inequalities on these variables.

$\endgroup$
  • $\begingroup$ Just a resource: or.deis.unibo.it/kp/Chapter6.pdf $\endgroup$ – fade2black Sep 13 '17 at 15:59
  • $\begingroup$ I'm more of a KP guy. I have seen many cases where both KP and LP were both used. Any insights on KP formulations? $\endgroup$ – Tina J Sep 13 '17 at 16:19
  • $\begingroup$ @TinaJ, what's KP? What is a KP formulation? $\endgroup$ – D.W. Sep 13 '17 at 19:34
  • $\begingroup$ Knapsack Problem. I was wondering if we can map it into a known variation of knapsack. $\endgroup$ – Tina J Sep 13 '17 at 21:34

Your Answer

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

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