数理最適化（組み合わせ最適化）

今回は組み合わせ最適化についてまとめていきます。
私がこれから解決していきたい問題が組み合わせ問題なので、初めにこちらを調べていきたいと思います。

組み合わせ最適化とは

あらためておさらいです。
組み合わせ最適化は、離散的な値を取る最適化問題のことを指します。
離散的な値とは、[0, 1, 3, ・・・] というようにとびとびの数値のことを言います。
有名な問題に、ナップサック問題というのがあります。
ナップサックに食料や道具等の物品を詰める際、ナップサックの許容重量範囲内でできるだけ有用な物を選ぶという問題です。

全ての組み合わせを調べればよいのでは？

組み合わせ問題なので、全ての組み合わせについて調べればいいんじゃないかと思いました。
この考えは、変数の種類が少ない場合はよさそうです。
しかし、私が解決したい問題はというと、
　変数の種類：基本的なもので約30　※細かいものも含めると50以上
　各変数の撮り得る値の種類：2～256
というように組み合わせの種類がとても多いです。
計算すると、100兆を超えます。
100兆というのは、1秒で10万組の算出ができたとしても、30年以上かかります。
とても待ちきれません。
このような現象を、「組み合わせ爆発」と呼びます。

組合せ爆発 - Wikipedia

組み合わせ最適化では、全組み合わせを確認しなくても、最適解を求めることができることを目指します。

組み合わせ問題の種類

• 巡回セールスマン問題：ある都市を出発し、全ての都市を訪問後に出発地点に帰還する場合、どのような順番で都市を回るのが最短経路であるか

• ナップサック問題：重量合計が規定を超えない範囲で品物の価値の合計を最大化する組み合わせをどのように選べばよいか

• 中国人郵便配達問題：頂点集合の一つのノ ードを出発し、全ての辺を通過し始点に戻る経路 の中で最小の経路を求める問題（巡回セールスマン問題との違いは、点と辺）

• 最小全域木問題：各枝に重みの与えられたグラフ上に存在する全域木の中で枝の重みの総和が最小になるものを見出す問題

• 最短経路問題：ある頂点から他の頂点への移動コストが最小になるような経路を求める問題

• 線型計画問題：目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題

• 整数計画問題：線型計画問題において、解ベクトルの各要素を整数に限定した問題（NP困難な問題

• 勤務スケジュール問題：ある条件を満たすある一定期間の勤務シフト表を作成する問題

などなど、いろいろあります。（もうおなかいっぱい）

問題の解き方

問題の解き方に、2種類あります。

①　厳密な最適解を求める方法
②　最適値に近い近似的な解を求める方法

メリット・デメリット

【①：厳密な最適解を求める方法】
・メリット　：最適解を求めることができます
・デメリット：答えを出すまでにかなりの時間を要する場合があります

【②：近似的な解を求める方法】
・メリット　：短い時間で答えを出すことができます
・デメリット：最適解ではないです

①厳密な最適解を求める方法

・分岐限定法
・動的計画法
など

②近似的な解を求める方法

・近似アルゴリズム
・ヒューリスティクス
など

絶対に最適解が必要な場合は、①。
ある程度良い解でよければ、②。
必要性が無ければ、②を選択した方がよさそうです。

次回は、解を求める方法について深堀していきたいと思います。