带有可替代物品的多个背包

Question

我正在使用 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 的物品。任何物品都可以与相同类型的物品交换。使用布尔变量对问题进行编码隐含地假设相同类型项目的分配顺序很重要。但实际上，顺序无关紧要，只会占用不必要的计算时间。

我想知道是否有任何方法可以设计模型，使其准确表达我们正在从可替代的项目池中进行分配以节省计算量。

Answer 1

不是为 bin 'b' 中类型 'i' 的 5 个项目创建 5 个布尔变量，而是从项目 'i' 的 0 到 5 个创建一个整数变量 'count'在 bin 'b' 中。那么sum over b (count[i][b]) == #item b

带有可替代物品的多个背包

Multiple Knapsacks with Fungible Items

or-tools