次元、要求、複数選択制約を含むナップサック問題: 一般化と定式化間の変換で説明されているように、複数選択ナップザック問題 (MCKP) を解決できるモデルをコーディングしようとしています(ここにあります。図 8 と 9 を参照してください)。基本的なナップザック問題の GMPL モデルの例をここで見つけることができます。ナップザックの問題の簡単な説明を探している人は、次の図を読んでください。
あなたは冒険家で、宝の山に出くわしました。それぞれが重み「w」と利益「p」を持つ何百もの素晴らしいアイテム「i」があります。耐荷重が 'c' のナップザックがあり、ナップザックに詰め込みすぎずに最大の利益を得たいとします。最も利益を上げられるアイテムの最適な組み合わせは何ですか?
コード内:
maximize obj :
sum{(i,w,p) in I} p*x[i];
ここで、「I」は商品のバスケットで、x[i] はバイナリ変数です (0 = 選択されていない、1 = 選択されている)
私が問題を抱えている問題は、複数のグループの追加です。MCKP では、各グループからアイテムを 1 つだけ選択する必要があります。たとえば、3 つのグループから選択するとします。それらは次のように表すことができます (実際の値は無視してください)。
# Items: index, weight, profit
set ONE :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;
# Items: index, weight, profit
set TWO :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;
# Items: index, weight, profit
set THREE :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;
各グループを反復処理する方法と、変数 x を定義する方法について混乱しています。次のようになると思います。
var x{i,j} binary;
ここで、i は j グループのアイテムのインデックスです。これは、一連のセットを定義することを前提としています。
set Groups{ONE,TWO,THREE}
次に、アイテムのグループを反復処理します。
sum{j in Groups, (i,w,p) in Groups[j]} p*x[i,j];
しかし、GMPL は順序集合をサポートしていないと思うので心配です。この関連する質問を見たことがあります。答えは、セット内でセットを定義することを示唆しています。ただし、この特定のシナリオでどのように適用されるかはわかりません。
明確にするために、私の主な質問: GMPL では、セットのセット (この場合、各グループがアイテムのセットを持つグループのセット) を反復処理するにはどうすればよいですか?