'Multiple Knapsack Problem with split weight
I am trying to solve a multiple knapsack problem with a variation.
- each item has a weight and a value
- only 1 item per bin
- the entire weight of an item must be used
- the weight of an item can be split across multiple bins
My variable is:
x = {(i, b): solver.IntVar(lb=0, ub=data['weights'][i], name=f'x_{i}_{b}') for i in data['all_items'] for b in data['all_bins']}
Using int instead of bool let me split weights between bins but I can't figure out how to constrain to 1 item per bin.
I tried creating a second variable y[i, b] as a boolean to mark if an item was in a bin but the constraint didn't work.
The constraint I tried using y[i, b]:
for b in data['all_bins']:
solver.Add(sum(y[i, b] for i in data['all_items']) <= 1)
And my objective is:
for i in data['all_items']:
for b in data['all_bins']:
objective.SetCoefficient(x[i, b], data['values'][i]/data['weights'][i])
objective.SetMaximization()
Any suggestions for how I can constrain to 1 item per bin?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
