数理最適化の入門知識まとめ(1)

数理最適化とは

• 与えられた制約条件の中で与えられた目的を最小化または最大化するもの
  ここで，制約条件と目的関数は数式を用いて表現できるものである（例えば，人の感覚値に基づいた定性的な評価は数式を用いて表現できない）

数理最適化の構成要素

数理最適化は以下の構成要素により成り立つ。これらについて以降で説明する。

1. 問題を把握する（ヒアリング，データ分析）
2. 数理モデルとして定式化
3. 定式化した数理モデルを解く
4. 得られた解を現実のオペレーションに落とし込む

数理モデルの定式化

• 解くべき問題において，決定する事柄を決定
  • 決定する事柄=決定変数
  • 数理最適化の目的は，決定変数の最適な値を求めること
• 決定変数を用いて，制約条件を数式(=制約式)で表す
  • 制約条件は**パラメータ(定数)**を用いて表す
• 決定変数を用いて，目的関数を数式で表す
  • 数理最適化の目的は，目的関数の最小化または最大化

数理最適化の一般系

• 決定変数: $x=(x_1, x_2, ...,x_n)$ ※n次元の実数ベクトル
• 目的関数: $f(x)$
• 制約条件:
  • $g_i(x)≤0 \quad i=1,2...,p$
  • $h_j(x)=0 \quad j=p+1,p+2,...p+q$

数理最適化問題は，これらの$p+q$本の制約式を満たす$x$の中で関数$f(x)$を最大にするものを求めること
関数$f(x)$を最大にする$x$を最適解，制約条件を満たす$x$のことを実行可能解という

線形計画問題と整数計画問題

• 線形計画問題: 目的関数が線形関数，制約式がすべて線形等式・線形不等式である数理最適化問題（線形と言いつつ様々な問題を定式化できる）
• 整数計画問題: 決定変数のうちいくつかに「整数でなければならない」という条件のついた線形計画問題

線形計画問題

• 目的関数: $\sum_{j=1}^{n}c_{j}x_{j}$
• 制約条件:
  • $\sum_{j=1}^{n}a_{kj}x_{j}≤b_k \quad k=1,2,...,p$
  • $\sum_{j=1}^{n}a_{lj}x_{j}=b_l \quad k=p+1,...,p+q$
  • $x_1≧0,x_2≧0,...,x_n≧0$

※整数計画問題: いくつかの変数$x$に整数でなければならないという制約が付いているもの

典型問題

集合分割問題

集合分割問題は、与えられた集合を複数の部分集合に分割する問題。目標は、各部分集合が特定の制約を満たすようにすること。
選択する候補の部分集合にはそれぞれコストがつけられており，その和を最小にするような部分集合を選ぶ。

例: $S = \{1, 2, 3, 4\}$ という集合があり、これを2つの部分集合に分割したいとする。それぞれの部分集合の合計が等しくなるように分割するのが目的。
つまり，以下のような候補の部分集合と書く部分集合にコストがつけられたときに，実行可能解(例えば$S_1$と$S_5$等)の中でコストが最小になる組み合わせを選ぶ。

数学的に表すと:

• 集合 $S$ を $k$ 個の部分集合 $S_1, S_2, ..., S_k$ に分割する
• 各部分集合 $S_i$ の合計ができるだけ均等になるようにする

目的関数:

$$\min \left( \max \left( \sum_{j \in S_i} x_j \right) - \min \left( \sum_{j \in S_i} x_j \right) \right)$$

制約:

$$\bigcup_{i=1}^{k} S_i = S \quad \text{and} \quad S_i \cap S_j = \emptyset \quad \forall i \neq j$$

ナップサック問題

ナップサック問題は、容量制限のあるナップサックに入れる物の組み合わせを最適化する問題。
つまり，容量制限を超えないように価値の合計が最大となる物の組み合わせを選ぶ。

例: 重さと価値がそれぞれ $(w_1, v_1), (w_2, v_2), ..., (w_n, v_n)$ で与えられる $n$ 個の物があり、ナップサックの最大容量が $W$ であるとする。価値の合計が最大になるように物を選ぶ。

目的関数:

$$\max \sum_{i=1}^{n} v_i x_i$$

制約:

$$\sum_{i=1}^{n} w_i x_i \leq W \quad \text{and} \quad x_i \in \{0, 1\}$$

ネットワーク最適化問題

ネットワーク最適化問題には、最短経路問題と最大流問題が含まれる。
ネットワークとは，点(ノード)の集合と2つの点を繋ぐ枝(エッジ)の集合により定められる。

• 有向ネットワーク：枝に向きがある(矢印になっている)ネットワーク ※(A,B)のように表される
• 無向ネットワーク：枝に向きがないネットワーク ※{A,B}のように表される

ネットワークにおいて，隣あう点AとBは点が隣接すると表現される。
枝には重み(コスト)が割り当てられる。

最短経路問題:

最短経路問題は、グラフの2つのノード間の最短経路を見つける問題。

• 例: グラフ $G = (V, E)$ で、各エッジに重み $w(e)$ が与えられている。ノード $s$ からノード $t$ への最短経路を求める。

目的関数:

$$\min \sum_{e \in P} w(e)$$

最大流問題:

最大流問題は、ネットワーク内のソース(スタート地点のノード)からシンク(ゴール地点のノード)への最大流量を求める問題。
エッジには容量が関連付けられ，流す量は容量を超えてはいけない。

• 例: 有向グラフ $G = (V, E)$ において、各エッジ $e$ に容量 $c(e)$ がある。ソース $s$ からシンク $t$ への最大流量を求める。

目的関数:

$$\max \sum_{e \in E} f(e)$$

制約:

$$f(e) \leq c(e) \quad \forall e \in E \quad \text{and} \quad \sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u) \quad \forall u \in V \setminus \{s, t\}$$

巡回セールスマン問題

巡回セールスマン問題は、全ての都市を一度だけ訪れて出発点に戻る最短経路を求める問題。
巡回路の移動距離はエッジの距離の総和で求められる。
都市数が少ない場合は，全パターンの移動距離を計算して求める方法をとることができるが，都市数が増えるとそれは難しい。
昨今は，整数計画問題として定式化する方法が洗練されており，かなりの数の都市があっても許容可能な時間で解ける。

例: $n$ 個の都市があり、各都市間の距離が行列 $D = (d_{ij})$ で与えられている。全都市を巡回して出発点に戻る際の総距離を最小化する。

目的関数:

$$\min \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ij}$$

制約:

$$\sum_{j=1, j \neq i}^{n} x_{ij} = 1 \quad \forall i \quad \text{and} \quad \sum_{i=1, i \neq j}^{n} x_{ij} = 1 \quad \forall j$$

$$\text{サブツアー制約}: \sum_{i, j \in S} x_{ij} \leq |S| - 1 \quad \forall S \subset V, |S| \geq 2$$

配送計画問題

配送計画問題は、複数の配送車が複数の顧客に複数の商品を届ける最適なルート(移動距離が最小となるルート)を求める問題。
どの顧客をどの配送者に割り当てるか，割り当てられた顧客をどの順序で訪問するか等を最適化する。

例: $m$ 台の配送車と $n$ 人の顧客があり、各顧客の需要と各配送車の容量が与えられている。全顧客の需要を満たすための最適なルートを求める。

目的関数:

$$\min \sum_{k=1}^{m} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ijk}$$

制約:

$$\sum_{k=1}^{m} \sum_{j=1}^{n} x_{ijk} = 1 \quad \forall i \quad \text{and} \quad \sum_{i=1}^{n} d_{ij} x_{ijk} \leq Q_k \quad \forall k$$

$$\text{サブツアー制約}: \sum_{i, j \in S} x_{ijk} \leq |S| - 1 \quad \forall S \subset V, |S| \geq 2, \forall k$$

これらの問題は、それぞれ異なるアプローチで最適化が行われ、現実世界のさまざまな応用に役立つ。