各グループが一意の要素セットを持つように、オブジェクトGroupのリストを含むデータ構造があるとします。Element
public class Group
{
public List<Element> Elements;
}
そして、特定の要素を必要とする母集団のリストを持っているとします。各母集団が必要な要素の固有のセットを持つようにします。
public class Population
{
public List<Element> RequiredElements;
}
定義された各グループの数量に制限はありません。つまり、集団によって消費されません。
特定の を見ているとしPopulationます。余分な要素が最小限に抑えられ、一致しない要素がないように、可能な限り最適なグループの一致を見つけたいと考えています。
例: 木材、鉄鋼、穀物、石炭を必要とする人口があります。使用可能なグループは、{wood, herbs}、{steel, coal, oil}、{grain, steel}、および {herbs, meat} のみです。
最後のグループ - {ハーブ、肉} は、私の集団ではまったく必要ないため、使用されていません。他のものはすべて必要ですが、ハーブとオイルは必要ないので無駄です。さらに、最小セットには鋼が 2 つ存在するため、1 ロットの鋼も無駄になります。この例のベスト マッチの無駄は 3 です。
そのため、数百Populationのオブジェクトの場合、最適な最小の無駄を見つけて、無駄になった要素の数を計算する必要があります。
どうすればこれを解決し始めることができますか? 一致が見つかったら、無駄を数えるのは簡単です。そもそもマッチを見つけるのは難しい。すべての可能性を列挙することはできますが、数千の集団と数百のグループがあるため、それはかなりの作業です。特に、このすべてがシミュレーテッド アニーリング アルゴリズムの各反復内にあることを考慮してください。
全体を混合整数プログラムとして定式化し、各反復で GLPK のようなソルバーを呼び出すことができるかどうか疑問に思っています。
問題を正しく説明できたことを願っています。不明な点は何でも明確にできます。
興味のある方のために、これが私のバイナリプログラムです...
x{0,1} の要素である決定ベクトルであり、問題の母集団がグループ i から受け取る/受け取らないことを示します。グループごとにエントリーがあります。
b{0,1} の要素である列ベクトルで、問題の母集団が必要とする/必要としないリソースを示します。リソースごとにエントリがあります。
A{0,1} の要素である行列で、どのリソースがどのグループに属しているかを示します。
プログラムは次のとおりです。
最小化: ((Ax - b)' * 1-ベクトル) + (x' * 1-ベクトル);
対象: Ax >= b;
制約は、必要なすべてのリソースが満たされなければならないことを示しているだけです。目的は、すべての余分なグループと使用されるグループの総数を最小限に抑えることです。(つまり、1 つのグループを使用した場合の 0 超過は、5 つのグループを使用した場合の 0 超過よりも優れています)。