CODEWITHSUNDEEP
or-toolscp-sat
Tom Bennett
Tom Bennett

Reputation: 2506

Multiple Knapsacks with Fungible Items

I am using cp_model to solve a problem very similar to the multiple-knapsack problem (https://developers.google.com/optimization/bin/multiple_knapsack). Just like in the example code, I use some boolean variables to encode membership:

# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data['items']:
    for j in data['bins']:
        x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

What is specific to my problem is that there are a large number of fungible items. There may be 5 items of type 1 and 10 items of type 2. Any item is exchangeable with items of the same type. Using the boolean variables to encode the problem implicitly assumes that the order of the assignment for the same type of items matter. But in fact, the order does not matter and only takes up unnecessary computation time.

I am wondering if there is any way to design the model so that it accurately expresses that we are allocating from fungible pools of items to save computation.

Upvotes: 0

Views: 100

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11014

Instead of creating 5 Boolean variables for 5 items of type 'i' in bin 'b', just create an integer variable 'count' from 0 to 5 of items 'i' in bin 'b'. Then sum over b (count[i][b]) == #item b

Upvotes: 2

Related Questions