Model Building in Mathematical Programming: 5.3 Network models

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

Chapter 5

5.3 Network models

数理最適化の問題にはネットワーク構造を持っているものが多い。PERT図におけるクリティカルパス分析とかはわかりやすいけど、わかりにくいけど実はネットワーク構造持っています、というものもある。例えば前に出てきた多期間問題とかもネットワーク構造を持っていたりする。そういった場合はLPとして定式化するよりもネットワーク用のアルゴリズムを使ったほうが高速（で、かつ場合に依っては理解しやすい）ことがあるので、どういう問題がネットワーク構造を持っているかを知っておいて、必要に応じてLPから書き換えられるようになっておくのは大事。

ただ、LPソルバー早いから、ネットワーク用のアルゴリズムを下手に独自実装しても勝てないことも多い。

ちなみにこの分野では、ネットワークをアークとノードという言葉で表現する模様。他の分野ではエッジとノードと言ったりする。説明するときに面倒くさいので、このへんの用語は統一してほしいなぁと前から思っている。

5.3.1 The transportation problem

輸送問題は典型的なネットワーク型の問題。輸送費の最小化とかはネットワークでいう最小費用流問題とみなすことができる。LPによる素直な定式化とネットワークだとみなしたときの定式化はとても似たものになるけど、資源制約に出てくる不等式を取り扱うために仮想的なノードを追加してあげるのがポイント。

生産計画などの多期間計画問題もネットワークとみなすことができる。具体的には、各期をノードと見立てて、その期の在庫等を次の期に持ち越す部分をアークに対応させる。言われてみればそのとおりだし、（数理計画を使わずに）頭で計画をねる時はそういうふうに考えると思うので自然なんだけど、言われないと気づかない。

ちなみに、ここに出てきた問題は（この後出てくるのもだいたいそうだけど）、LPとして解いても、結局最適解は整数になるようなことが多い。LPとIPだとIPのほうが解くのが難しいから、LPとして定式化するけど整数が出てくるという性質はとても嬉しい。単体法を考えると、LPって結局成約同士の交点から最適なものを選んでいるわけで、交点が整数しかないなら最適解は必然的に整数になる。

5.3.2 The assignment problem

仕事をアサインするような問題は、仕事と人の2部グラフとみなすことができるので、ネットワーク構造があるといえる。

5.3.3 The transhipment problem

店舗と工場があったときに、別工場を経由して店舗に輸送するような経路もあるような問題。2部グラフにならないだけで、 transportation problem と同じ。

5.3.4 The minimum cost flow problem

ネットワークとして書き下せるかは、結局うまく目的関数を設定できるかに尽きると思った。ネットワーク用のアルゴリズムは、結局最小費用流とか有名所の目的を達成するためのアルゴリズムなので、たとえ問題がネットワーク構造を持っていたとしても、目的関数が複雑怪奇だったとしたら、効率的に計算できるアルゴリズムは存在しないかもしれない。

5.3.5 The shortest path problem

総流量を1にして、minimum cost flow を解けば、 shortest path problem を解いたことになる。なるほど。

5.3.6 Maximum flow through a network

各アークに流量の容量制約がある場合に、どうやって流すのが最大か、という話。

5.3.7 Critical path analysis

これだけ、いままでのやつと定式化のしかたがちょっと違て、タスクの開始時刻を変数としている。最適解における各タスクの開始時刻はわかったけど、クリティカルパスをどうやって見つけるのかはちゃんと書いていなかった気がするので、もう一度読み直してみる。

5.4 Converting linear programs to networks

特定の形のLPとして定式化された問題をネットワークとして書き直す手順が書かれている。ネットワークとして書き直せれば、ネットワーク用のアルゴリズムが使えるので嬉しいよね、という話だが、正直その心というか、なぜこれでうまくいくのかが直感的に理解できなかったので、手を動かしてみるしかなさそう。

ちなみに、LPを自動的にネットワークに書き直すのは結構大変で、書き直すこと自体が、問題を直接解くよりも計算コストがかかってしまうのが知られているらしい。

TODO

12.19 Distribution 1 をやる
問題を1つピックアップして、5.4の方法でネットワークに変換してみる