Model Building in Mathematical Programming: 4.2 〜 4.3
Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。
ブログ書くのを一週間放置していたら、せっかく議論した内容の7割くらいわすれていてさみしかったので、来週はもうちょっと早めに更新します。
Chapter 4
4.2 Stochastic programses
実際の数理最適化のプロジェクトでは、与えられるデータに不確実性が含まれることが多い。例えば、前章で扱った多期間問題はその典型で、。そういった状況で、不確実性をモデルに組み込む方法の1つに確率計画法 (Stochastic Programming) がある。
不確実なデータの取りうる値が離散化できる場合は、以下のようにする。
- 可能性のある値それぞれに対応する変数をすべて用意する。
- 上記の変数に確率値を掛け算することで、期待値としたものを目的関数に用いる
ただし、多期間問題のような状況では、考える期間の指数オーダーで変数が増えるので注意が必要。
ロバスト最適化と呼ばれる方法とも関係があるが、ロバスト最適化の場合は、データの不確実性に対する解の安定性を評価することが多く、この方法は不確実性が定量化できなかったとしても適用可能。 Section 6.3 で感度分析を取り扱うので、多分そこで出てくる。
4.3 Decomposing a large model
この章では、 Dantzig-Wolfe 分解というアルゴリズムについて学んだ。
Section 4.1 で出てきたような、構造を持っているようなモデルは、サブモデルに分解することで、効率的に解を探索できる可能性がある。
ではどうやってサブモデルに分解するかというと、有名な手法が2つあって、割当による分解(decomposition by allocation, Rosen(1964)) と価格による分解(decomposition by pricing, もしくは Dantzig-Wolfe分解)。
割当による分解は直感的だが、この本で具体的に扱っているのは Dantzig-Wolfe 分解の方。
いわゆる列生成法と呼ばれる手法（列生成法についてはこちらの資料がわかりやすい）。マルチプラントモデルを例にとれば、全体で最適な生産計画を練ろうとすると、
- 各プラントにどれだけの原材料を配分して、
- 各プラントで何をどれだけ作るかを決める
必要がある。 逆に言うと、この2つの問題を解けば、全体で最適な生産計画が得られることになる。 1. のことを主問題、2. のことを子問題と呼ぶ。Dantzig-Wolfe分解では、主問題で原材料の配分割合を直接指定する代わりに、原材料の価格(internal price) という変数を定義して、ちょうどいい配分になるような価格を探る問題として解く。
この辺の話は双対問題で考えると考えやすい（実際、前述の列生成法の資料でも双対問題を解いている）と思うけど、この本ではそういった話はしていなかったのもあり、著者の思惑をきちんと理解できたかはかなりあやしい。なんとか直感的に理解したいものだが。。
分散計画経済の話が出てきたが、きちんと理解できていない。ただ、米国の電力会社などでそれに似た事例が報告されているらしい。
日本でも米国でも、事例を集めるのはとても有意義な気がするので、やってみよう。
今回も自分が発表担当したので、当日の発表資料 も合わせてご覧ください。
TODO
- 宿題: 12.24 Yield management を解く
- Chapter 5 を読む
- Dantzig-Wolfe分解について、双対の概念なしに、図形的に理解できないか、もうちょっと頑張ってみる。
