始めに

言わずもがな問題を定義することは重要
特に、言語化や可視化するだけではなく、
問題の目的や制約、関係や構造を定式化することが大切
その定式化の分野としては数理最適化が有名

数理最適化とは

数理最適化は「ある制約が存在する中で、数ある答えの中から最も良いものを見つける」ための手法
昔からオペレーションズ・リサーチなどの分野で研究されてきた
この分野は、経営学、工学、経済学、コンピュータ科学など様々な分野で応用
英語ではMathematical Optimizationと言う

数理最適化の流れ

最適化問題の求解プロセスは、次のようなプロセスに従う。

問題の把握
問題のモデル化
適用手法の選択
手法の実現と適用
意思決定

最適化問題の求解プロセス

最終的にそれらを基に意思決定を行う（最適解を出す）。
また、それらの実験的を繰り返して行う。

移動方法の選択の問題の例

問題の把握

問題は、大阪-東京間の最適な移動方法選択である。

まずは問題を把握する。

その問題の目的は何であり
どのような制限があり
何が固定で、何を決定するのか

例えば、次などの事項を明らかにする。

移動にかかる時間を最短としたいのか、それとも経費を最小としたいのか
使用可能な経費の上限はいくらか
移動手段を決定するのか、あるいは、それは定まっていて、利用する便を決定するのか

問題のモデル化

問題において本質的でない部分を削ぎ落とし、定量的な表現を可能とする
何らかの計算手法を適用する場合には、一般には式として表現する
ここでは一般化した例を示す

$$ \newcommand{\br}{\\} \begin{align*} \text{minimize (または maximize)} & \quad f(x) \br \text{subject to} & \quad g_i(x) \leq 0, \quad i = 1, 2, \ldots, m, \br & \quad x \in X. \end{align*} $$

ここで、変数はそれぞれ次を表わす。

$x$は決定変数
$f(i)$は目的変数
$g_i(x)$は制約条件
$X$は決定変数の定義域

最適化問題はこれらの要素の特徴に基づいて分類される。

適用手法の選択

問題のモデルに基づいて、適切な求解手法を選択する
この例では、時刻表を調べて適切な便を選択することも考えられる
特別な制約条件がないのであれば、WEB上のサービスを使うことも可能である

手法の実現と適用

何らかの手法の適用において、複数のアルゴリズムが使用可能であることが多い
その場合、アルゴリズムを選択し、またそこにパラメータが含まれているのであれば、その値を決定した上で対象モデルに適用する
この例では、自分で時刻表を調べるとしたとき、便を探すための手順（目次を見る、前から順に探すなど）に相当すると考えられる

意志決定

手法を適用することで得られた結果が適切であるか否かを判断する
このような行為の主体は、意思決定者（Decision Maker; DM）と呼ばれる
その結果が適切であれば、それが対象とする最適化問題の最適解であるといえる

ナップザック問題の例

問題の把握

おそらく最も有名なのはナップザック問題
次に例題を示す

商品の仕入れのため、9kgまで入るバックを持って店を出た。
商品には以下の4種類があり、1度の仕入れで商品価値が最も高くなるよう仕入れたい。

商品Aは重さが2kgで、商品価値は3万円
商品Bは重さが3kgで、商品価値は4万円
商品Cは重さが4kgで、商品価値は6万円
商品Dは重さが5kgで、商品価値は7万円

つまり、限られた容量（この場合はバッグの重さが9kgまで）の中で、
最も価値の高いアイテムの組み合わせを選ぶことが目的。

問題のモデル化

まとめると次になる。

決定変数：持っていくか行かないかの二値と、その個数
目的：商品価値が最も高くなるよう仕入れる
制約条件：9kgまでしかバックに入らない

それを定式化すると次になる。

$$ \newcommand{\br}{\\} \begin{align*} \text{maximize} & \quad \sum_{i=1}^{n} v_i x_i \br \text{subject to} & \quad \sum_{i=1}^{n} w_i x_i \leq W, \br & \quad x_i \in {0, 1}, \quad i = 1, 2, \ldots, n. \end{align*} $$

ここで変数はそれぞれ以下を示す。

$x_i$は各商品$i$を持っていくか行かないかの決定
$n$は商品の総数
$v_i$は商品$i$の価値
$w_i$は商品$i$の重量
$W$はバッグの最大容量

適用手法の選択

ナップザック問題は、一般的に、整数計画問題（Integer Programming）の一種
アイテムは完全に持って行くか、まったく持って行かないかのどちらかを取るため線形ではないため
整数計画問題はPythonのpulpライブラリが実装しているsolverで解く事が可能

手法の実現と適用

それをPythonで解くと次になる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import pulp

def solve_knapsack_with_pulp(weights, values, max_weight):
    n = len(weights)
    prob = pulp.LpProblem("KnapsackProblem", pulp.LpMaximize)
    item_vars = pulp.LpVariable.dicts("Items", range(n), 0, 1, pulp.LpBinary)
    prob += pulp.lpSum([values[i] * item_vars[i] for i in range(n)]), "TotalValue"
    prob += pulp.lpSum([weights[i] * item_vars[i] for i in range(n)]) <= max_weight, "TotalWeight"
    prob.solve()
    total_value = pulp.value(prob.objective)
    items_selected = [i for i in range(n) if pulp.value(item_vars[i]) == 1]
    return total_value, items_selected

weights = [2, 3, 4, 5]  # kg
values = [30_000, 40_000, 60_000, 70_000] # JPY
max_weight = 9 # kg
max_value_pulp, items_selected_pulp = solve_knapsack_with_pulp(weights, values, max_weight)
max_value_pulp, items_selected_pulp

上を実行すると以下になる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>> max_value_pulp, items_selected_pulp = solve_knapsack_with_pulp(weights, values, max_weight)
Result - Optimal solution found

Objective value:                130000.00000000
Enumerated nodes:               0
Total iterations:               1
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00
>>> max_value_pulp
130000.0
>>> items_selected_pulp
[0, 1, 2]

最適な商品の組み合わせが商品A（index=0）、商品B（index=1）、商品C（index-2）であった
この組み合わせで得られる総価値は13万円であった

意思決定

結論としては、商品A、B、Cをを仕入れれば良い

その他

形式化と定式化の違い

形式化（Formalization）
- 形式化は、ある概念、問題、または理論を厳密な形式
- 特に数学的または論理的な形式に置き換えるプロセス
定式化（Formulation）
- 定式化は、より一般的な用語
- ある理論、方針、計画、またはアイデアを明確かつ具体的な言葉や形式で表現すること

まとめ

定式化の例として移動方法の選択とナップザック問題について説明した
ナップザック問題は、持っていくか行かないかの二値分類問題なので、広義の意味でのAIである
高級なAIのモデルを使わずとも、古典的アルゴによって簡便に解ける問題であった
AIの前に問題の目的や制約を定式化するのが大切

定式化のすゝめ

目次

始めに

数理最適化とは

数理最適化の流れ

移動方法の選択の問題の例

問題の把握

問題のモデル化

適用手法の選択

手法の実現と適用

意志決定

ナップザック問題の例

問題の把握

問題のモデル化

適用手法の選択

手法の実現と適用

意思決定

その他

形式化と定式化の違い

まとめ

参考文献