'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