Блог

Я использую cp_model для решения проблемы, очень похожей на проблему с несколькими рюкзаками (https://developers.google.com/optimization/bin/multiple_knapsack ). Как и в примере кода, я использую некоторые логические переменные для кодирования членства:

 # 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))
  

Специфика моей проблемы заключается в том, что существует большое количество взаимозаменяемых предметов. Может быть 5 предметов типа 1 и 10 предметов типа 2. Любой предмет можно заменить предметами того же типа. Использование логических переменных для кодирования проблемы неявно предполагает, что порядок присвоения для элементов одного и того же типа имеет значение. Но на самом деле порядок не имеет значения и только отнимает ненужное вычислительное время.

Мне интересно, есть ли какой-либо способ спроектировать модель так, чтобы она точно выражала, что мы выделяем из взаимозаменяемых пулов элементов для экономии вычислений.

Вместо создания 5 логических переменных для 5 элементов типа ‘i’ в ячейке ‘b’, просто создайте целочисленную переменную ‘count’ от 0 до 5 элементов ‘i’ в ячейке ‘b’. Затем sum over b (count[i][b]) == #item b