複数のバックパックと制約がある種類のナップザック問題を解決する

Question

私は、Excelソルバーまたは他のツール（任意の提案は歓迎です）で解決したい次の問題がありますが、コードを書くことはしません。

私はいくつかのバックパック（約5）に入れるためにいくつかのアイテム（約40個）を持っています。 すべてのアイテムの重量は異なりますが、すべてのバックパックには同じスペースがあります。

アイテムの重量の合計は、バックパックの容量よりはるかに少ないです。

私がしなければならないことは、バックパックにアイテムを配分して、すべて同じものを多かれ少なかれ同じにすることです。換言すれば、分散を減少させる。

いくつかのアイテムは一緒に使用できないという制約があります。 私は一緒に行くことができるかできない項目のリスト（または隣接行列）を持っています。

もちろん、1つのアイテムがバックパックに入っていると、2番目のアイテムには行けません（アイテムの各キングには1つのアイテムしかありません）。

私はこの問題をExcelソルバーで解決しようとしていますが、3つのアルゴリズムのすべてが解決策を見つけることができないと言いますが、手作業で見つけることができるので正しく設定していないと思います。

とにかく私は体重に関する問題の部分だけをExcelで設定できますが、項目間の非互換性に関する問題の部分を設定することはできません。

はあなたの助け

Answer 1

これはナップザックよりもサイドの制約とmultiprocessor scheduling以上でいただきありがとうございます。

こういう単純な処方を試すことができます。それぞれの品目には、その品目がどのバックパックに入っているかを示す0-1変数とその合計が1になるという制約があります。目的は、バックパックの最大総重量を最小限に抑えることです。一緒に行くことのできないアイテムのペアごとに、対応するインジケータ変数の合計が1以下である[バックパック数]制約があります。

ここでは2つのバックパックB）、3つのアイテム（x、ウェイト3; y、ウェイト1、およびz、ウェイト4）、および1つの競合（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であり、正しい数のバックパックと1つのバックパックを拘束するための部分問題を正確にカバーすることになるマスター問題がありますが、これはExcelの対象外です。