CODEWITHSUNDEEP
pythonoptimizationconstraintsor-tools
pythonislovepythonislife
pythonislovepythonislife

Reputation: 121

How to compare set() and list() in Google Or Tools?

I am working on specific multi bin knapsack problem using Google Or Tools.

One of constraints assumes that items are split into parts and only one part of item can be stored in single bin.

I've created additional list that represents item ids. So, for example:

items = [1, 2, 3, 4]
item_ids = [1, 1, 2, 2]

means that we have two items splitted into 2 parts each.

After that I want to use constraint that forces list of stored items ids to be the same as set of stored items ids.

Something like:

solver.Add(
   [matrix[i][j] * data['items_ids'][i] for i in data['items']] == \
   list(set([matrix[i][j] * data['items_ids'][i] for i in data['items']]))
)

(data is dictionary like in https://developers.google.com/optimization/bin/multiple_knapsack)

And I am getting error below:

    File "optimiser.py", line 111, in define_constrains
      list(set([matrix[i][j] * data['items_ids'][i] for i in data['items']]))
TypeError: unhashable type: 'ProductCst'

I believe it's because result of matrix[i][j] * data['items_ids'][i] is not a number but Google Or Tools class but I have no idea how to get list of unique values of Google Or tools variables.

Upvotes: 1

Views: 552

Answers (1)

pythonislovepythonislife
pythonislovepythonislife

Reputation: 121

I've solved it by changing conception of solution.

As @sascha mentioned in comments, Or-tools is not doing dimensionality-repairing tricks so I've changed my approach.

I've added constraint for every part of item:

def item_parts_in_bin(i, j, data, matrix):
    return sum(
        matrix[_i][j] for _i in data['items']
        if data['item_ids'][i] == data['item_ids'][_i]
    )

for i in data['items']:
    solver.Add(
        item_parts_in_bin(i, j, data, matrix) <= 1
    )

So basically it returns count of item parts of same item id placed in bin. This sum must be <= 1 that means that only one part of item can be in the bin at the same time.

Upvotes: 1

Related Questions