解决一种具有多个背包和约束的背包概率
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.