組合せ最適化 - 典型問題と実行方法

  • 72
    Like
  • 1
    Comment

組合せ最適化の典型問題と実行方法

組合せ最適化における典型問題と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を実行してください。
Dockerのインストールに関しては、DockerでJupyterを起動するまでも参考にしてください。

ローカルにインストールし実行する場合

下記ソフトウェアをインストールしてください。

  • Anaconda
    • Pythonおよび科学技術用各種パッケージを統合したディストリビューション
    • 利用したいバージョンのインストーラーを実行する。
  • pip install pulp
    • 数理最適化用のモデラーおよびソルバー。
  • pip install ortoolpy
    • 典型問題用。最低限の機能のものや効率の悪いものも含まれている。

参考