Python
最適化

pyomoとglpkを使ってナップサック問題を解く

More than 1 year has passed since last update.

最適化モデリング言語であるpyomoを用いれば、変数・制約条件・目的関数を指定するだけである程度の最適化問題を解くことができます。ここでは例としてナップサック問題を解いてみます。

インストール

# pip install Pyomo
# pacman -S glpk

glpkは最適化問題を解くためのソルバーです。pyomoで記述された問題をglpkで解きます。

pyomoによるコード

mkp_concrete.py
from pyomo.environ import *

v = {'applepie':8, 'beer':3, 'chocolatecake':6, 'duckmeat':11}
w = {'applepie':5, 'beer':7, 'chocolatecake':4, 'duckmeat':3}

limit = 14

M = ConcreteModel()
M.I = Set(initialize=v.keys())
M.x = Var(M.I, within=Binary)
M.value = Objective(expr=sum(v[i]*M.x[i] for i in M.I), sense=maximize)
M.weight = Constraint(expr=sum(w[i]*M.x[i] for i in M.I) <= limit)

コードの説明

pyomoでは、具体モデルか抽象モデルのどちらかを選択することができます。ConcreteModelは具体モデルを意味します。

Setはアイテムの集合を意味し、Varは変数を意味します。within=Binaryで変数のタイプを指定していますが、ここでは0-1変数により、カバンに入れるアイテムであるか否かを定義しています。

Objectiveは目的関数です。ナップサック問題の目的関数は、バッグに入れるアイテムの価値の合計値の最大化となります。sense=maximizeにより最大化を指定しています。

Constraintは制約条件です。ナップサック問題の制約条件は、重さの合計値が指定値以下であることを意味します。

コードの実行と実行結果

実行.
$ pyomo solve --solver=glpk mkp_concrete.py

[    0.00] Setting up Pyomo environment
[    0.00] Applying Pyomo preprocessing actions
[    0.01] Creating model
[    0.01] Applying solver
[    0.03] Processing results
    Number of solutions: 1
    Solution Information
      Gap: 0.0
      Status: optimal
      Function Value: 25.0
    Solver results file: results.json
[    0.03] Applying Pyomo postprocessing actions
[    0.03] Pyomo Finished

実行結果は以下のファイルに格納されます。

results.json
{
    "Problem": [
        {
            "Lower bound": 25.0,
            "Name": "unknown",
            "Number of constraints": 2,
            "Number of nonzeros": 5,
            "Number of objectives": 1,
            "Number of variables": 5,
            "Sense": "maximize",
            "Upper bound": 25.0
        }
    ],
    "Solution": [
        {
            "number of solutions": 1,
            "number of solutions displayed": 1
        },
        {
            "Constraint": "No values",
            "Gap": 0.0,
            "Message": null,
            "Objective": {
                "value": {
                    "Value": 25.0
                }
            },
            "Problem": {},
            "Status": "optimal",
            "Variable": {
                "x[applepie]": {
                    "Value": 1.0
                },
                "x[chocolatecake]": {
                    "Value": 1.0
                },
                "x[duckmeat]": {
                    "Value": 1.0
                }
            }
        }
    ],
    "Solver": [
        {
            "Error rc": 0,
            "Statistics": {
                "Branch and bound": {
                    "Number of bounded subproblems": "1",
                    "Number of created subproblems": "1"
                }
            },
            "Status": "ok",
            "Termination condition": "optimal",
            "Time": 0.007568359375
        }
    ]
}

結果の解釈

上記結果は、以下のように解釈できます。

"applepie, chocolatecake, duckmeatをカバンに入れることにより、最大の価値25.0を得る。"

pyomoの良いところ

gurobi optimizerのほうが質が良いのですが、pyomoは無料で使うことができます。

最適化モデリング言語は、ソルバーに問題を解かせるためにモデルを記述します。つまり、ソルバーがやってくれる部分のアルゴリズムを考える必要はありません。

言い換えれば、pyomoやgurobi optimizerを使えば、問題のモデル化のみに集中すればよいことになります。

速度の面からいえば、アルゴリズムを選定してやるほうが早くなる場合がありますが、ソルバーにやらせる方法もある程度の速度はあります。