[最適化問題のすゝめ：第1部] 数理最適化とは？種類や特徴を解説

みなさんは数理最適化や最適化問題ということばをご存知でしょうか。
おそらく「最適化ということばは、よく聞くけれど詳しくはしらない」という方が多いのではないかと思います。

数理最適化という道具を用いて作成する問題を最適化問題と呼びます。最適化問題は、考えないといけない制約が複数ある状態で、ある目的を最大・最小にしたいオーダがある際に役立ちます。実際に具体例を挙げてみます。

• コンビニへ商品配送におけるルート最適化問題
• カーナビのルート探索
• 工場の製品機器への割り当て問題
• 病院で働く看護時のシフト勤務問題

想像していたより実社会における適用範囲が広いと感じたのではないでしょうか。
今回は、数理最適化のことをより深く知っていただけるように、２部構成の記事を組みました。

第一部では数理最適化の特徴や種類のお話、最適化と密接に関係してくるソルバのお話をしたあと、有名な「どろぼうの問題（ナップザック問題）」を通して最適化への理解を深めることができる流れになっています。

第二部目では第一部にて学んだ内容を踏襲しつつ、著者が作成したオリジナル問題を通してより汎用的な最適化問題を解き、興味・理解を深めていただければと思っています。

数理最適化っておいしいの？

冒頭「はじめに」でも、最適化問題について少し説明しました。ここでは、もう少し詳しい数理最適化について（特徴や種類）説明していきます。

最適化問題は、目的関数、制約条件で構成されています。

• 目的関数：考えている問題には、目的（最大や最小）がある
• 制約条件：考えている問題には、守るべき制約がある。

つまり、最適化問題は「制約条件の下で目的関数を最良にする状態を求める問題」と表すことができます。そして、この最良な状態のことを最適解といいます

では、数理最適化問題（以降では最適化問題と呼ぶことにします）には、どのような問題の種類があるのか見てみましょう。最適化問題は、目的関数、制約条件や変数の状態によって問題の種類を分類できます。また、問題ごとに解や分析アプローチが違ってくることも特徴です。

ここで少し変数の種類についてお話をしておくことにします。変数には連続変数と整数変数（離散変数と呼ぶこともあります）があります。連続変数とは、その名の通り「変数値が連続的に変わりうるもの、任意の値を取りうるもの」のことをさします。例えば、体重などがそうです。45kgととることもできるし、45.5kgや45.0000005kgととることもできます。一方、整数変数とは「変数値が整数値に限定されるもの」のことをさします。例えば人数やさいころの目（６面）などがそうです。一般的に人数は1人、2人….と数えますね、とびとびに人数をカウントすることは、特殊な状況ではない限り、まずありませんね。

また、離散変数には、スイッチのON/OFFのような役割をする0-1変数というものがあります。この0-1変数をうまく利用する事で、そのままでは記述することが難しい目的関数や制約式を表現できる場合があります。

最適化ソルバって食べれるの？

ここでは、最適化問題と綿密に関わってくる最適化ソルバについて説明します。最適化ソルバは、最適化問題の最適解を得るために用いるソフトウェアのことです。もちろん、簡単な線形問題、列挙するべき組合せ数が少ない問題等なら、ソルバを使わずに手で解くこともできます。しかし、手作業で問題で解くことは現実的ではないので、そのような問題であっても最適化ソルバを使用することによって、より早く解を得られる可能性が高まります。

ソルバに関する特徴や種類を下記の表にまとめました。無償のものから有償（商用・アカデミック利用）という違い、解ける問題の種類や対応するOSなどの違いもあることが特徴です。本記事では、無償のソルバであるGLPKを用いています。

最適化問題＆最適化ソルバ

ここでは、最適化問題とソルバをどのような手順で使用していくのか、簡単に説明します。おおまかな過程は、下記のようになっています。

まず、実際の問題を最適化問題として定式化します。そして定式化したものをソルバが読み込める形で書く作業（モデリング）を行います。次に、ソルバにモデルを読み込ませて最適解を求めます。最後にソルバを用いて算出された解を分析し、結果に応じてパラメータの調整や制約の追加や削除を行います。このような工程を繰り返すことで、より精緻で実世界に即したモデルにすることができ、実問題に寄り添った最適解を得ることができるでしょう。

どろぼうの問題の定式化

ここからは有名な「どろぼうの問題」（世の中では「ナップザック問題」と呼ばれています）通して、より詳しい最適化問題の世界を理解していきましょう。まずは、下記の「どろぼうの問題」を読んでみましょう。

では、上記の問題文からどのように定式化するのか見てみましょう。どの部分がどこと対応しているのか、問題文と照らし合わせてみてください。

上記のような記号を定義したとき以下のように定式化することができる。

詳しい式の説明をしていきます。制約条件(1.1)は、かばんの耐えれる重さに関する制約です。(1.1)式の左辺を分解すると、w₀x₀ + w₁ x₁ + w₂ x₂ + w₃ x₃ + w₄ x₄の5項で構成されていますね。ここで登場するのが前述した0-1変数です。例えば、お宝番号0をカバンにつめるときx₀=1になります。このとき第1項は、w₀の重さが加算され12×1=12となります。逆に、お宝0をカバンにつめない場合はx_i=0になりますので、重さがいくらであろうとw_ix_iの項は0になります。制約条件の(1.2)は、制約条件(1.1)にでてきたx_iが0-1変数であるという意味を示します。

目的関数の説明をします。本問題を読むと「一番価値のあるお宝の組合せを選んで持ち帰ることにしました….」とあります。つまり目的関数は、選んだお宝の価値の合計値を最大にするような式にする必要がありますね。ここでまた登場するのが0-1変数であるx_iです。制約条件(1.1)で具体的に説明した場合と同様に構成し（今回はx_iに乗ずる値はw_iではなくv_iになっていますが）、うまく式が表現できていることがわかります。

このようにして、うまく0-1変数を使用すれば実際の問題を定式化できましたね。

ソルバを用いた最適化計算

さて、問題の定式化が終わりましたので、次の工程である「ソルバ計算」に進みます。先ほど定式化したものを、ソルバが読み込めるように「モデリング」と呼ばれる作業が必要になります。モデリングの方法は「どのようにしてソルバを利用するか」によって作業内容が変わってきます。今回紹介するソルバの利用方法の流れは下記の2つです。

1. モデリングに特化した言語：AMPLを用いてモデリングし、CUIを利用してソルバ呼び出しを行い最適化計算、解の算出を行う。
2. API（Python言語）を利用してモデリングからソルバ計算と解の算出までを行う。

各項目の特徴、利点や欠点等を列挙し簡単に説明します。

1.CUIを利用してソルバ計算

「AMPL言語ってどんな感じなんだろう？」と思われた方もいるかもしれないので、どろぼうの問題をAMPL言語で記述してみました。

#############
# モデルファイル(.mod)
#############
# 集合
set I;
# パラメータ
param w{I};
param v{I};
param W;
# 変数
var x{I} binary;

# 目的関数
maximize Objective:
     sum{i in I} v{i} * x{i};
# 制約条件
subject to C1:
    sum{i in I} w{i}*x{i} <= W;

#############
# データファイル(.dat)
#############
# 集合
set I := 0, 1, 2, 3, 4;

# パラメータ
param w :=
0 12
1   2
2   1
3   1
4   4
;
param v :=
0   4
1   2
2   2
3   1
4  10
;
param W := 15
;

AMPL言語を用いてCUIでソルバ（今回はGLPKを使用します）を呼び出す場合は、定式化した内容をモデルファイルとデータファイルに分けて記述する必要があります。

モデルファイルには、集合、パラメータと変数の宣言をし、定式化した数式を記述します。一方データファイルには、モデルファイルに記述した集合とパラメータの要素を記述します。書き方には少しルールがあり、慣れるまでは記述が難しいかもしれません。

このようにモデル・データファイルの記述ができたら、ソルバを呼び出します。呼び出し方は、OSによって違いますがwindows環境とmac環境では違います（ダウンロードを含めた詳しい情報は、ここにかかれています）。mac環境だと以下のコマンド、GLPKソルバを呼び出すことができます。呼び出し時には、入力ファイル（モデルファイルとデータファイル）や出力ファイルの指定ができます。

$ glpsol -m ***.mod -d ***_dat -o ***result.txt --log ***log.txt

記述にミス等がなくうまく入力ファイルを読み込み解をみつけることができていれば、最適化計算が始まります。計算が終わると「INTEGER OPTIMAL SOLUTION FOUND」とコンソールに出力されるはずです。計算時に指定した出力ファイル（解ファイルとログファイル）もディレクトリに出力されているでしょう。

2.APIを利用してソルバ計算

今度は、pulpと呼ばれるPythonライブラリをモデリングに使用して、先ほど定式化した「どろぼうの問題」をモデリングしてみましょう。

# パッケージ
from pulp import *
# 数理モデルのクラスの定義
m = LpProblem(sense=LpMaximize)

# パラメータの設定
w = [4, 2, 2, 1, 10]  # 重さ
v = [12, 2, 1, 1, 4]   # 価値
# 変数の定義
r = range(len(w))
x = [LpVariable('x%d'%i, cat=LpBinary) for i in r]

# 制約条件
W = 15
m += lpDot(w, x) <= W
# 目的関数
m += lpDot(v, x)

# ソルバで計算する
m.solve()
# 解出力
print('得られる価値: {}'.format(value(m.objective)))
print('カバンにつめるお宝番号: {}'.format([i for i in r if value(x[i]) > 0.5]))

# 実行結果のステータスを参照
m.status
LpStatus[m.status]

このようにしてモデリングすることができます。記述にミス等がなくうまく入力ファイルを読み込むことができていれば、コンソールには解「得られる価値: 17.0 カバンにつめるお宝番号: [0, 3, 4]と’Optimal’」が表示されるはずです。よく見ると、pulpの記述方式では、Σ（シグマ）を「lpDot」で、0-1変数であることの指定を「LpVariable」を用いて表現していますね。このような表現は、使用するライブラリによって異なるのが特徴です。

ここまでで、最適化問題やソルバについて、最適化問題の定式化と①と②の2種類のソルバの呼び出し方法について説明してきました。では、どちらの形式の呼び出し方をすれば良いのかは、悩むポイントだと思います。著者しても、どちらも利点と欠点があり、使用環境や好みなどの違いもあるため、どちらがベストなのかは決めるのが難しいのが現実ですね。

まとめ

いかがでしょか、最適化問題について少し興味がわいてきたでしょうか。
第二部目では第一部にて学んだ内容を踏襲しつつ、著者が作成したオリジナル問題を通してより汎用的な最適化問題を解き、興味・理解を深めていただければと思っています。

[最適化問題のすゝめ：第2部] 数理最適化の問題を解いて理解を深めよう

執筆者：山本