私は、複数選択の多次元ナップザック問題のいくつかの (比較的簡単な) インスタンスを解決しようとしています (グループごとに 1 つのアイテムのみを取得できるアイテムのグループがあり、アイテムの重量はナップザックと同様に多次元です)容量）。処方と解決策に関して 2 つの質問があります。
- 2 つのグループのアイテム数が異なる場合、アイテム数の少ないグループに、利益がゼロで重み = 容量のアイテムを入れて、問題を行列形式で表現することはできますか? これはソリューションに影響しますか? 具体的には、最適化プログラムがあると仮定します。最初のグループ (項目セット) には 3 つの候補項目があり、2 番目のグループには 2 つの項目 (3 つとは異なる) があります。つまり、これらは次の形式を持ちます。
最大化 (x_ij を超える) {v_11 x_11 + v_12 x_12 + v_13 x_13 +
v_21 x_21 + v_22 x_22}
{w^i_11 x_11 + w^i_12 x_12 + w^i_13 x_13 + w^i_21 x_21 + w^i_22 x_22 <= W^i, i=1,2 に従う
x_11 + x_12 + x_13 = 1, x_21 + x_22 = 1, x_ij \in {0,1} for all i and j.
このシナリオでは、値 v_23 = 0 および w^1_23 = W^1、w^2_23 = W^2 の人為的なアイテム x_23 を追加して、完全な製品 v_ij x_ij (i=1,2 j=1,2 ,3)?
- (1) が可能であるとすると、cvx などのオープンソースの最適化パッケージを使用してインスタンスを解決しようとした人はいますか? 私は cplex について知っていますが、学問以外の人が入手するのは難しく、GLPK が変数のグループをサポートするかどうかはわかりません。