解决一种具有多个背包和约束的背包概率
Solving a kind of knapsack prob with multiple backpacks and constraints
我有以下问题，我想用 excel 求解器或任何其他工具解决（欢迎任何建议），但我不想编写代码。
我有几件物品（大约40件）要放在几个背包里（大约5件）。
每件物品的重量都不同，但每个背包的重量都相同 space。
物品的重量总和远小于背包的容量。
我需要做的是分配背包中的物品，使它们的重量大致相同。换句话说，减少方差。
有一个限制：有些项目不能放在一起。
我有一个可以或不能放在一起的项目的列表（或邻接矩阵）。
当然，一旦一个物品进入背包就不能进入第二个（每个物品王只有一个物品）。
我正在尝试使用 excel 求解器来解决这个问题，但是所有 3 个算法都说它们无法找到解决方案，但我可以手动找到它们，所以我认为我没有正确配置。
反正我在excel中只能配置关于权重的部分问题，但是我无法设置关于项目之间不兼容问题的部分。
感谢您的帮助
这比背包更 multiprocessor scheduling 具有侧面限制。
您可以尝试这样一个天真的公式。对于每个项目，有 [背包数量] 0-1 个变量指示该项目在哪个背包中，以及这些变量总和为 1 的约束。 objective 是为了最小化背包中的最大总重量。对于每对不能一起走的物品，有[背包数量]个约束，对应的指标变量之和小于等于1。
这是一个工作示例，其中包含两个背包（A 和 B）、三件物品（x，重量 3；y，重量 1；z，重量 4）和一个冲突（x 不能与 y 搭配）。
minimize C
over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C
subject to
C >= 3*Ax + 1*Ay + 4*Az # load in A
C >= 3*Bx + 1*By + 4*Bz # load in B
Ax + Bx = 1 # one placement of x
Ay + By = 1 # one placement of y
Az + Bz = 1 # one placement of z
Ax + Ay <= 1 # conflict between x and y in A
Bx + By <= 1 # conflict between x and y in B
这个公式不是最优的，因为没有对称性破缺——本质上，LP 求解器的搜索树被复制了一个等于背包排列数的因子。这只有5个！ = 120 在你最坏的情况下，虽然，所以它可能没问题。要走的路可能 column generation 有一个主问题，相当于用正确数量的背包精确覆盖物品，还有一个子问题，相当于打包一个背包受约束，但这超出了 Excel.
我有以下问题，我想用 excel 求解器或任何其他工具解决（欢迎任何建议），但我不想编写代码。
我有几件物品（大约40件）要放在几个背包里（大约5件）。 每件物品的重量都不同，但每个背包的重量都相同 space。
物品的重量总和远小于背包的容量。
我需要做的是分配背包中的物品，使它们的重量大致相同。换句话说，减少方差。
有一个限制：有些项目不能放在一起。 我有一个可以或不能放在一起的项目的列表（或邻接矩阵）。
当然，一旦一个物品进入背包就不能进入第二个（每个物品王只有一个物品）。
我正在尝试使用 excel 求解器来解决这个问题，但是所有 3 个算法都说它们无法找到解决方案，但我可以手动找到它们，所以我认为我没有正确配置。
反正我在excel中只能配置关于权重的部分问题，但是我无法设置关于项目之间不兼容问题的部分。
感谢您的帮助
这比背包更 multiprocessor scheduling 具有侧面限制。
您可以尝试这样一个天真的公式。对于每个项目，有 [背包数量] 0-1 个变量指示该项目在哪个背包中，以及这些变量总和为 1 的约束。 objective 是为了最小化背包中的最大总重量。对于每对不能一起走的物品，有[背包数量]个约束，对应的指标变量之和小于等于1。
这是一个工作示例，其中包含两个背包（A 和 B）、三件物品（x，重量 3；y，重量 1；z，重量 4）和一个冲突（x 不能与 y 搭配）。
minimize C
over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C
subject to
C >= 3*Ax + 1*Ay + 4*Az # load in A
C >= 3*Bx + 1*By + 4*Bz # load in B
Ax + Bx = 1 # one placement of x
Ay + By = 1 # one placement of y
Az + Bz = 1 # one placement of z
Ax + Ay <= 1 # conflict between x and y in A
Bx + By <= 1 # conflict between x and y in B
这个公式不是最优的，因为没有对称性破缺——本质上，LP 求解器的搜索树被复制了一个等于背包排列数的因子。这只有5个！ = 120 在你最坏的情况下，虽然，所以它可能没问题。要走的路可能 column generation 有一个主问题，相当于用正确数量的背包精确覆盖物品，还有一个子问题，相当于打包一个背包受约束，但这超出了 Excel.