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

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

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

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

目的関数

考えている問題には、目的（最大や最小）がある

制約条件

考えている問題には、守るべき制約がある

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

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

ここで、少し変数の種類についての話をしておきましょう。

変数には連続変数と整数変数（離散変数と呼ぶこともあります）があります。連続変数とは、その名の通り「変数値が連続的に変わりうるもの、任意の値を取りうるもの」のことを指します。例えば体重などがそうです。45kgと取ることもできるし、45.5kgや45.0000005kgと取ることもできます。一方、整数変数とは「変数値が整数値に限定されるもの」のことを指します。例えば人数やサイコロの目（6面）などがそうです。一般的に、人数は1人、2人、3人…と数えます。飛び飛びに人数をカウントすることは、特殊な状況ではない限りまずありません。

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

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

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

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

特徴

• 無償・有償／得意問題（線形・非線形問題）／対応OSが違う

• 最適化ソルバはほとんどが海外で作られている

• 複数のソルバ性能を比較するための「ベンチマーク」問題集（混合整数計画問題）がある

種類

• 無償：GLPK、MIPCL、SCIPなど

• 有償：FICO, Gurobi、CPLEX、IPOPT、KNITRO、SNOPTなど

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

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

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

どろぼうの問題の定式化

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

問題文

お宝があると噂に聞いた泥棒が、ある豪邸に忍び込みました。しかし、予想していた以上にお宝の種類があることがわかりました。重いお宝、大きいお宝、小さいけど価値があるお宝…。どうやら、お宝の種類は全部で5つあり、それぞれの価値と価格は下記の表のとおりです。あいにく、5つすべてのお宝は入りきらないようです。

そこで泥棒は、カバンの容量と耐えられる重さを考えたうえで、一番価値のあるお宝の組み合わせを選んで持ち帰ることにしました。ただし、カバンの耐えられる重さは15とします。

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

記号

• 集合

  • お宝の集合I

• 変数

  • お宝をカバンに詰めるとき1、詰めないとき0を意味する0-1変数x_i

• パラメータ

  • お宝の重さと価値をそれぞれw_i, v_i

  • カバンの耐えられる重さをW

定式化

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

$$\text{maximize}\sum _{i\in I}^{}{v}_i{x}_i$$ $$\text{subject to}\sum _{i\in I}^{}{w}_i{x}_i\le W\text{—– (1.1)}$$ $$x_i\in \{0,1\}(i\in I)\text{—– (1.2)}$$

詳しい式の説明をしていきます。制約条件 (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つです。

CUIを利用してソルバ計算

AMPL（モデリングに特化した言語）を用いてモデリングし、CUIを利用してソルバ呼び出しを行い最適化計算、解の算出を行う。

APIを利用してソルバ計算

API（Python言語）を利用してモデリングからソルバ計算と解の算出までを行う。

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

CUIを利用してソルバ計算

特徴

• モデル記述にAMPLを使用。

• ソルバの呼び出しはCUIで行う。

• 解・ログファイルは、ソルバ特有の記述方式。

利点

• モデル記述にAMPLと呼ばれるモデリング言語を用いることができる。

• Python等のAPIを用いていないため、解の算出までが高速で行える。

欠点

• 解・ログファイルから必要な情報のみを取り出すのが面倒。

• AMPLは、記述方法を覚える・慣れるまでは大変。

• 無償で利用できるソルバの種類が少ない。

「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」とコンソールに出力されるはずです。計算時に指定した出力ファイル（解ファイルとログファイル）もディレクトリに出力されているでしょう。

APIを利用してソルバ計算

特徴

• モデリングからソルバ計算と解算出には、Python言語を用いることができる。

• 線形計画問題を解くためのPythonライブラリは、多種多様（mypulp, cbc, Scipy, Pymo…）なのが特徴。

利点

• モデル記述から解出力まで、Python言語を用いることができる。

• 線形計画問題を解くためのPythonライブラリに付随するソルバが性能が良いことが多い。

欠点

• モデル中でfor文の入れ子が何重（ネスト）になると、計算時間が増加する。

今度は、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部目では第1部にて学んだ内容を踏襲しつつ、オリジナル問題を通してより汎用的な最適化問題を解き、興味・理解を深めていただければと思っています。

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