組合せ最適化の典型問題と実行方法
組合せ最適化における典型問題とPythonによる実行方法の一覧を上げる。(実行してみよう)
より詳しい説明については、書籍「組合せ最適化」を参考のこと。
| 典型問題クラス | # | 典型問題 | 複雑性クラス | 双対問題 |
| グラフ・ネットワーク問題 | 1 | 最小全域木問題 | P | |
| 2 |
最大安定集合問題 (最小頂点被覆問題, 補グラフの最大クリーク問題) |
NP困難 | ||
| 3 | 最大カット問題 | NP困難 | ||
| 4 | 最短路問題 | P | ||
| 5 | 最大流問題 | P | 最小カット問題 | |
| 6 | 最小費用流問題 | P | ||
| 経路問題 | 7 | 運搬経路(配送最適化)問題 | NP困難 | |
| 8 | 巡回セールスマン問題 | NP困難 | ||
| 9 | 中国人郵便配達問題 | P | ||
| 集合被覆・分割問題 | 10 | 集合被覆問題 | NP困難 | 11 | 集合分割問題 | NP困難 |
| 12 | 組合せオークション問題 | NP困難 | ||
| スケジューリング問題 | 13 | ジョブショップ問題 | NP困難 | |
| 14 | 勤務スケジューリング問題 | NP困難 | ||
| 切出し・詰込み問題 | 15 | ナップサック問題 | NP困難 | |
| 16 | ビンパッキング問題 | NP困難 | ||
| 17 | n次元詰込み問題 | NP困難 | ||
| 配置問題 | 18 | 施設配置問題 | NP困難 | |
| 19 | 容量制約なし施設配置問題 | NP困難 | ||
| 割当・マッチング問題 | 20 | 2次割当問題 | NP困難 | |
| 21 | 一般化割当問題 | NP困難 | ||
| 22 | 最大マッチング問題 | P | ||
| 23 | 重みマッチング問題 | P | ||
| 24 | 安定マッチング問題 | (P) |
- 最大安定集合問題の解で選ばれなかったノードは最小頂点被覆問題の解となる。
- 配送最適化を配送計画のように、XX最適化をXX計画と呼ぶことも多いが、XX計画は古い呼び方となる。
実行してみよう
Dockerから起動する場合
Docker Toolboxをインストールし、Kitematicから、Dockerイメージtsutomu7/typical_optimizationを実行してください。
実行したら http://localhost:8888 を開いてください。Jupyter Notebook のパスワードは jupyter です。
Dockerのインストールに関しては、DockerでJupyterを起動するまでも参考にしてください。
ローカルにインストールし実行する場合
下記ソフトウェアをインストールしてください。インストール後は、上記の各問題のリンク先のコードを実行できます。
-
Python本体とpipのインストール：環境構築ガイドで対象OSを選んでインストールしてください。
- バージョンは3系の最新版をおすすめします。ただし、いくつかのライブラリーは最新版だと動かないことがあるので、その場合は古いバージョンの方が安定します。
-
ライブラリーのインストール：
pip install pandas matplotlib jupyter more-itertools scipy networkx ortoolpy-
ortoolpy：典型問題用。最低限の機能のものや効率の悪いものも含まれている。PuLP（数理最適化用のモデラーおよびソルバー）もインストールされます。
-
参考：Anacondaを使う方法もありますが、ライブラリーの管理が上記の方法と異なります（Anacondaは、Pythonおよび科学技術用各種パッケージを統合したディストリビューションです）。
-