離散最適化問題の理論と応用

1. はじめに

離散最適化問題は、現代の情報科学、経済学、運輸学、工学など、さまざまな分野で広く研究されている重要なテーマです。これは、問題の解が離散的（整数や有限個の選択肢の中から選ばれる）であり、目的関数を最大化または最小化するための最適な解を求める問題です。本記事では、離散最適化問題の基礎理論、代表的なアルゴリズム、そして現実世界での応用例について初心者にもわかりやすく解説します。

2. 離散最適化問題の概要

2.1 離散最適化とは

離散最適化問題では、解が整数または離散的な値を取ります。例えば、物品の選択、ルートの決定、タスクのスケジューリングなど、選択肢が明確に限定されている場合にこの手法が用いられます。

離散最適化問題を定式化するためには、まず次の3つの要素を定義します。

決定変数: 解を構成する変数で、通常は整数値または有限の集合から選ばれます。
目的関数: 決定変数の組み合わせに対して計算される評価指標であり、これを最大化または最小化します。
制約条件: 決定変数が満たすべき条件や制限で、これにより解の範囲が制限されます。

2.2 例: ナップサック問題

ナップサック問題は離散最適化問題の代表例です。ここでは、重さと価値が異なる複数のアイテムがあり、容量が限られたナップサックにこれらのアイテムを入れる場合、価値の総和が最大となるようにアイテムを選ぶことが目標です。

問題の定式化

$x_i$をアイテム$i$を選ぶかどうかを示す二値変数（$x_i \in {0, 1}$）とします。
各アイテム$i$の価値を$v_i$、重さを$w_i$、ナップサックの容量を$W$とします。

目的関数は、価値の総和を最大化することです。

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

制約条件は、選んだアイテムの重さがナップサックの容量を超えないことです。

$$
\sum_{i=1}^{n} w_i x_i \leq W
$$

この問題の解は、制約条件を満たしつつ、目的関数の値が最大となるような$x_i$の組み合わせです。

3. 離散最適化問題の基本理論

3.1 組合せ最適化とNP困難問題

多くの離散最適化問題は、組合せ最適化問題と呼ばれるカテゴリーに属し、解空間が非常に大きく、全ての解を列挙することが現実的ではありません。特に、NP困難問題（非決定性多項式時間で解けるが、その解を見つけるのは難しい問題）に属するものが多く、効率的なアルゴリズムが存在しないと考えられています。

3.2 線形計画法と整数計画法

線形計画法（Linear Programming, LP）は、連続変数を用いた最適化手法であり、解空間が凸である場合に非常に効率的に解くことができます。これに対し、整数計画法（Integer Programming, IP）は、解が整数である場合に適用されますが、整数制約があるため、計算が難しくなります。

線形計画法の定式化

一般的な線形計画問題は以下のように表現されます。

$$
\text{maximize} \ c^T x \
\text{subject to} \ Ax \leq b, \ x \geq 0
$$

ここで、$x$は決定変数のベクトル、$c$は目的関数の係数ベクトル、$A$は制約条件を定める係数行列、$b$は制約の右辺ベクトルです。

整数計画法の拡張

整数計画法では、線形計画法に整数制約が追加されます。

$$
\text{maximize} \ c^T x \
\text{subject to} \ Ax \leq b, \ x \geq 0, \ x \in \mathbb{Z}^n
$$

ここで、$x \in \mathbb{Z}^n$は$x$が整数値であることを意味します。

4. 離散最適化問題の代表的なアルゴリズム

4.1 分枝限定法

分枝限定法（Branch and Bound）は、整数計画問題を解くための古典的なアルゴリズムです。この方法は、問題を部分問題に分割し、それぞれの部分問題を解くことで最適解を探索します。

アルゴリズムの概要

問題を解空間の探索木として表現し、根からスタートします。
部分問題に分割し、それぞれを評価します。
部分問題の解が制約条件を満たさない場合、その部分問題を除外します（このプロセスを「枝刈り」と呼びます）。
全ての部分問題を評価し、最良の解を選びます。

分枝限定法は、最悪の場合でも全ての可能な解を評価することなく、最適解を見つけることができる場合があります。

4.2 動的計画法

動的計画法（Dynamic Programming, DP）は、問題を複数のサブプロブレムに分割し、それらを順に解くことで最適解を求める手法です。ナップサック問題や最短経路問題などで用いられることが多いです。

ナップサック問題への適用

ナップサック問題に動的計画法を適用する場合、次のように解を構築します。

重さ$w$までの容量に対する最適価値$V(w)$を計算する。
次の再帰関係を用いる。

$$
V(w) = \max(V(w), V(w – w_i) + v_i)
$$

これを全てのアイテム$i$に対して繰り返すことで、最適な解を求めることができます。

4.3 メタヒューリスティック

メタヒューリスティック（Metaheuristics）は、局所最適解に陥ることなく広範な解空間を探索するためのアルゴリズムの総称です。特に、大規模な問題やNP困難問題に対して有効です。

代表的なメタヒューリスティック

遺伝的アルゴリズム（Genetic Algorithm, GA）: 生物進化のプロセスを模倣した手法で、選択、交叉、突然変異を通じて最適解を探索します。
シミュレーテッドアニーリング（Simulated Annealing, SA）: 物理学の焼きなまし過程を模倣し、高温から徐々に冷却することで最適解を探索します。
タブーサーチ（Tabu Search）: 直前の解を「タブー」として記憶し、同じ解を繰り返し探索しないようにします。