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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Just a resource: or.deis.unibo.it/kp/Chapter6.pdf $\endgroup$
    – fade2black
    Commented Sep 13, 2017 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
    Commented Sep 13, 2017 at 16:19
  • $\begingroup$ @TinaJ, what's KP? What is a KP formulation? $\endgroup$
    – D.W. ♦
    Commented Sep 13, 2017 at 19:34
  • $\begingroup$ Knapsack Problem. I was wondering if we can map it into a known variation of knapsack. $\endgroup$
    – Tina J
    Commented Sep 13, 2017 at 21:34
  • $\begingroup$ @fade2black thats a terrible resource. You have to start reading that book from the start to understand what they are on about by chapter 6. Also, its heavily academic with a focus on complexity theory. There seems to be very little work done on this problem in layman terms. Also, this problem is NP-Complete so this solution will only be tractable with very low number. Your better off with a greedy approach i.e. sort by value/weight and then allocate. $\endgroup$
    – CpILL
    Commented Sep 14, 2019 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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