解決一種具有多個揹包和約束的揹包問題

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的範圍。