patternMinor
Multi- Knapsack problem variation
Viewed 0 times
knapsackmultiproblemvariation
Problem
I'm trying to model a scenario where there are
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#81186, answer score: 2
Revisions (0)
No revisions yet.