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

# 組合せ最適化の典型問題と実行方法
[組合せ最適化](http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721)における典型問題とPythonによる実行方法の一覧を上げる。([実行してみよう](#実行してみよう))
より詳しい説明については、書籍[「組合せ最適化」](http://www.amazon.co.jp/dp/4061565443)を参考のこと。

<table>
<tr><td>典型問題クラス</td><td>#</td><td>典型問題</td><td>複雑性クラス</td><td><a href="http://qiita.com/SaitoTsutomu/items/d1812ff9b5ccf0ecc716">双対問題</a></td></tr>
<tr><td rowspan='6'>グラフ・ネットワーク問題</td>
    <td>1</td><td><a href='3130634debf561608bd9'>最小全域木問題</a></td><td>P</td><td></td></tr>
<tr><td>2</td><td><a href='33ad03bcaa421eb2ba17'>最大安定集合問題</a><br>(<a href='179db1bd283ab4d926d1'>最小頂点被覆問題</a>, 補グラフの最大クリーク問題)</td><td>NP困難</td><td></td></tr>
<tr><td>3</td><td><a href='d716413c4b93b22eaad3'>最大カット問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>4</td><td><a href='565c59fac36badb6a80c'>最短路問題</a></td><td>P</td><td></td></tr>
<tr><td>5</td><td><a href='80e70da6717acacefa00'>最大流問題</a></td><td>P</td><td><a href='eb1d96e35cb24bed35ae'>最小カット問題</a></td></tr>
<tr><td>6</td><td><a href='41d625df63f1946c7216'>最小費用流問題</a></td><td>P</td><td></td></tr>
<tr><td rowspan='3'>経路問題</td>
    <td>7</td><td><a href='1126e1493ff601a858c9'>運搬経路(配送最適化)問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>8</td><td><a href='def581796ef079e85d02'>巡回セールスマン問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>9</td><td><a href='6b8e4a9c794ff8be110f'>中国人郵便配達問題</a></td><td>P
</td><td></td></tr>
<tr><td rowspan='3'>集合被覆・分割問題</td>
    <td>10</td><td><a href='b1f3a24aaf50afd93e09'>集合被覆問題</a></td><td>NP困難</td><td></td></tr>
    <td>11</td><td><a href='22ec0e42999141a0ba1e'>集合分割問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>12</td><td><a href='614aa24b4025d3f7cc73'>組合せオークション問題</a></td><td>NP困難</td><td></td></tr>
<tr><td rowspan='2'>スケジューリング問題</td>
    <td>13</td><td><a href='d088959bf884d40b2053'>ジョブショップ問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>14</td><td><a href='e79ad9ca61a82d5482fa'>勤務スケジューリング問題</a><td>NP困難</td><td></td></td></tr>
<tr><td rowspan='3'>切出し・詰込み問題</td>
    <td>15</td><td><a href='d3c07494e7ba992bf19d'>ナップサック問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>16</td><td><a href='36788d01fb3be80564a1'>ビンパッキング問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>17</td><td><a href='0ac9bd564ae9f91285d7'>n次元詰込み問題</a></td><td>NP困難</td><td></td></tr>
<tr><td rowspan='2'>配置問題</td>
    <td>18</td><td><a href='c5055be8144e085274c1'>施設配置問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>19</td><td><a href='0cbd2e9a75ef0ecb3269'>容量制約なし施設配置問題</a><td>NP困難</td><td></td></td></tr>
<tr><td rowspan='5'>割当・マッチング問題</td>
    <td>20</td><td><a href='3814e0bb137be0c18f02'>2次割当問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>21</td><td><a href='329eb7f49af673a19cb8'>一般化割当問題</a></td><td>NP困難</td><td></td></tr>
<tr><td>22</td><td><a href='37262bef6f2cab331e01'>最大マッチング問題</a></td><td>P</td><td></td></tr>
<tr><td>23</td><td><a href='bbebc69ebc2549b0d5d2'>重みマッチング問題</a></td><td>P</td><td></td></tr>
<tr><td>24</td><td><a href='2ec5f7626054f4b4de63'>安定マッチング問題</a></td><td>(P)</td><td></td></tr>
</table>

- 最大安定集合問題の解で選ばれなかったノードは最小頂点被覆問題の解となる。
- 配送最適化を配送計画のように、XX最適化をXX計画と呼ぶことも多いが、XX計画は古い呼び方となる。

# 実行してみよう
## Dockerから起動する場合
[Docker Toolbox](https://www.docker.com/docker-toolbox)をインストールし、Kitematicから、Dockerイメージ[tsutomu7/typical_optimization](https://hub.docker.com/r/tsutomu7/typical_optimization/)を実行してください。
実行したら `http://localhost:8888` を開いてください。Jupyter Notebook のパスワードは `jupyter` です。
Dockerのインストールに関しては、[DockerでJupyterを起動するまで](http://qiita.com/SaitoTsutomu/items/29414e2d4f30b2bc94ae)も参考にしてください。

## ローカルにインストールし実行する場合
下記ソフトウェアをインストールしてください。インストール後は、上記の各問題のリンク先のコードを実行できます。

- Python本体とpipのインストール：[環境構築ガイド](https://www.python.jp/install/install.html)で対象OSを選んでインストールしてください。
  - バージョンは3系の最新版をおすすめします。ただし、いくつかのライブラリーは最新版だと動かないことがあるので、その場合は古いバージョンの方が安定します。
- ライブラリーのインストール：
  `pip install pandas matplotlib jupyter more-itertools scipy networkx ortoolpy`

  - ortoolpy：典型問題用。最低限の機能のものや効率の悪いものも含まれている。PuLP（数理最適化用のモデラーおよびソルバー）もインストールされます。

  - 参考：[Anaconda](http://continuum.io/downloads#py34)を使う方法もありますが、ライブラリーの管理が上記の方法と異なります（Anacondaは、Pythonおよび科学技術用各種パッケージを統合したディストリビューションです）。

# 参考

- [数理最適化モデラー PuLP チートシート](http://qiita.com/SaitoTsutomu/items/c0bbf6cf8873ccd7edf3)