【Python】基本的な整数最適化問題を解いてみる

Pythonを使って、基本的な整数最適化問題の一つである多制約ナップサック問題を解いてみます。後半に参考書籍も紹介しています。

多制約ナップサック問題

多制約ナップサック問題は、以下のように定式化できます。

maximize Σvixi
subject to Σwkixi ≤ ci, ∀ i ∈ I　　xk ∈ {0, 1}, ∀ k ∈ K

Iはアイテム番号の集合、vはアイテムの価値、wは制約の重み、Kは制約番号の集合、cは制約の上限値です。k ≥ 2 で多制約となります。

例題

荷物を9 kgまで、かつ7000 ㎤まで入れられるナップサックがあるとします。以下の4つの商品からナップサックに入れる商品を選ぶ時、価格の合計が最大となる組み合わせを求めます。

	商品1	商品2	商品3	商品4
価格 / 円	8,000	10,000	15,000	20,000
重量 / kg	3	4	5	6
体積 / ㎤	2,000	2,500	3,800	4,500

ナップサックに入れる商品1～4の個数をx1～x4とすると最適化対象の目的関数と制約条件は以下のとおりとなります。

maximize
8,000 × x1 + 10,000 × x2 + 15,000 × x3 + 20,000 × x4

制約式は以下のとおりとなります。

subject to
3 × x1 + 4 × x2 + 5 × x3 + 6 × x4 ≤ 9
2000 × x1 + 2500 × x2 + 3800 × x3 + 4500 × x4 ≤ 7000
xk ∈ {0, 1}, ∀ k ∈ {1, 2, 3, 4}

Python実装

動作確認したpython、モジュールのバージョンは以下のとおりです。

python 3.6.0
mypulp 0.0.9

Pythonで実装します。mypulpというモジュールを使用しますため、インストールしておきます。

pip install mypulp

続いて最適化計算を実装します。

from mypulp import *

def mkp(I, v, w, K, c):
    """
    多制約ナップサックモデルの生成
    :param I:アイテム番号
    :param v:アイテムの価値
    :param w:制約の重み
    :param K:制約番号
    :param c:制約の上限値
    :return:多制約ナップサックモデル
    """
    model = Model()
    x = {}

    # 変数
    for i in I:
        x[i] = model.addVar(vtype='B', name=''.join(['x', str(i)]))

    # 制約
    for k in K:
        model.addConstr(quicksum(w[k, i] * x[i] for i in I) <= c[k])

    model.setObjective(quicksum(v[i] * x[i] for i in I), GRB.MAXIMIZE)
    model.update()

    return model


if __name__ == '__main__':
    # 条件・パラメータ設定
    I, v = multidict({1: 8000, 2: 10000, 3: 15000, 4: 20000})
    w = {(1, 1): 3, (1, 2): 4, (1, 3): 5, (1, 4): 6,
         (2, 1): 2000, (2, 2): 2500, (2, 3): 3800, (2, 4): 4500,
         }
    K, c = multidict({1: 9, 2: 7000})

    # モデル生成
    model = mkp(I, v, w, K, c)
    
    # 最適化
    model.optimize()

    # モデルのファイル出力
    model.write('mkp.lp')

    for v in model.getVars():
        print(v.VarName, ':', v.X)
    print('Optimized value', ':', model.ObjVal)

コードの実行結果は以下のとおりです。

x1 : 1.0
x2 : 0.0
x3 : 0.0
x4 : 1.0
Optimized value : 28000.0

x1とx4を入れることで、ナップサック内の合計価格が28,000円に最大化されることがわかりました。

また、mkp.lp ファイルの中身は以下のとおりです。

\*  *\
Maximize
OBJ: 8000 x1 + 10000 x2 + 15000 x3 + 20000 x4
Subject To
c_1: 3 x1 + 4 x2 + 5 x3 + 6 x4 <= 9
c_2: 2000 x1 + 2500 x2 + 3800 x3 + 4500 x4 <= 7000
Binaries
x1
x2
x3
x4
End

モデルが正しいかどうか確認する場合に役立ちます。