解决一种具有多个背包和约束的背包问题

Question

我有以下问题，我想用Excel解算器或任何其他工具解决（任何建议是受欢迎的），但我不想写代码。

我有几个项目（约40）放在几个背包（约5）。 每个项目都有不同的重量，但每个背包都有相同的空间。

物品重量的总和远小于背包的容量。

我需要做的是在背包中分配物品，填充所有物品的重量差不多。换句话说，减少方差。

有一个约束：有些项目不能在一起。 我有一个列表（或邻接矩阵）的项目可以或不可以一起去。

当然，一件物品放在背包里不能进入第二件物品（每件物品只有一件物品）。

我试图用excel求解器解决这个问题，但所有3个算法都说他们找不到解决方案，但是手动找到它们，所以我认为我没有正确配置。

无论如何，我只能在excel中配置有关权重问题的部分，但我无法设置有关项目之间不兼容问题的部分。

谢谢您的帮助

Answer 1

这是一种比背包侧约束的更多multiprocessor scheduling。

你可以试试像这样天真的表述。对于每个项目，有[背包数量] 0-1个变量，指示该项目在哪个背包中，以及这些变量总和为1的约束。目标是最小化背包中的最大总重量。对于每对不能放在一起的项目，有[背包数量]限制，即相应指示变量的总和小于或等于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的范围。