LoginSignup
219

More than 3 years have passed since last update.

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

Last updated at Posted at 2015-07-10

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

組合せ最適化における典型問題と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および科学技術用各種パッケージを統合したディストリビューションです)。

参考

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
219