0-8

Model Building in Mathematical Programming: Chapter 7

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

Chapter 7 Non-linear models

ここでは、非線形問題をどうやって線形な問題に変形するか、関数の凸性等について学んだ

7.1 Typical applications

目的関数が線形の場合、スケールによるメリットやデメリットを表現できない。例えば、目的関数が利益だった場合、

目的関数が線形である == 生産量が少なくても多くても、1単位あたりの利益は同じ

という意味だ。現実的には、生産量が多くなるほど1単位あたりのコストが下がったり、逆にリソースの取り合いが発生してコストが上がったりする。

価格弾力性  E _ {x} は以下の式で定義される

 E _ {x} = \frac{\rm 需要の変化量}{\rm 価格の変化量}

これがある範囲で一定だと思うと、適正な価格は  p(x) = kx^{-1/E_x} という形となるので、目的関数には、  p(x)x = kx^{1-1/E_x} のような項が入ってくることになる。

他の例だと、2つ以上の原料を混ぜ合わせて新しいものをつくる混合問題で、硬さなどの指標が必ずしも各原料の割合に比例するわけではない場合や、地理情報を入れる場合に、多項式の項が出てきたりする。

7.2 Local and global optima

ここでは、凸性の定義などを確認した。凸であることがとても大事だというお話だ。

7.3 Separable programming

ここは短いけれども結構面白かった。 まず、 separable (分離可能)とは、1変数の関数の和の形であらわせる関数のこと。例えば  x ^ 2 _ 1 + 2 x _ 2 は separable だが、  x_1 x_2 + x_2 / (1 + x _ 1) は separable ではない。

separable だと、非線形な項があったとしても、該当する変数を適当に分割して、区分線形の形にして解くことができる。

区分線形の形にするのは、凸だとかんたんだけど、非凸だと途端に面倒になって、整数計画法がでてきたりするので嫌だ。

ちなみに、非線形である とか 凸である とかいう話は目的関数だけでなく、制約式の方も含んだ話のはず。

7.4 Converting a problem to a separable

 x _ 1 x _ 2 みたいな項があったとしても、実は変数を追加することで、 separable な形に変形することができる。具体的には

 
u_1 = x_1 + x_ 2 \\
u_2 = x_1 - x_2

みたいな変数を追加して、  x _ i を置き換える。この時全ての  x _ i を置換する必要はない (上式を成約に入れておけば十分)。変数が3つ以上に増えても、同様の方法が使える。ただし変数が多くなるので注意。

TODO

  1. 宿題: 12.21 Agricultural pricing をとく

Model Building in Mathematical Programming: 6.4〜6.5

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

Chapter 6

6.4 Further investigations using a model

ここまでの解析では、

  1. 同時に1つの変数のみを動かす
  2. 動かす範囲には限度がある

という制限があったが、Parametric Programming を使うとこの制限を超えてモデルを解析できるらしい。かんたんな例だとイメージしやすい。例えば 96時間研磨の時間を増やすには、48時間分の労働が必要、といった場合には  \theta ( 96, 48 ) みたいな方向に制約右辺を動かせば良い。

6.5 Presentation of the solutions

レポートライターなるプログラムがあるよ。

宿題 12.15 Tariff rates (power generation)

電力の需要を推定しつつ、発電量を調整する問題。 Tariff をどう訳すべきなのかがわからなかった。起動時のみかかるコストなどもあり、現実的な問題で面白かった。

colab.research.google.com

Model Building in Mathematical Programming: 6.1 〜 6.3

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

Optimization Night #3 等に現をうかしていたため、2周分まとめての更新です。

Chapter 6

6.1 Validating a model

モデルの検証ちゃんとやりましょうというお話。とっても大事。モデルは大きく分けて3つある。

  1. Infeasible models
    • 実行可能解が存在しないような場合、たいてい間違っている。なぜなら、数理最適化って今人手でやっている仕事を置き換えることが多いから。いま人手でやっているのは最適とは限らないが実行可能解のはず。定式化が間違っている可能性が高い。
    • ちなみに、違反している制約を列挙するのは簡単だが、その原因を見つけるのは数式からだけだととても難しい。なぜなら、infeasibleになるのは制約1つではなく制約の組み合わせに依って発生するから。
    • だからこそ、制約を聞きつつ、過去データ(人手でやってきた記録)を入手しておくのがとても大事。過去データを入力してみて、違反している制約がないか確認する。
  2. unbounded models
    • 今度はいくらでも解を良くできてしまう場合。だいたいの場合、制約を追加し忘れている。
    • ソルバーがある程度頑張ったところで解を出力してくれるので、その解を見ながら、抜けている制約を検討する。結構極端な値になるので、制約を見つけるのは簡単なことが多そう。
  3. solvable models
    • 最適解がえられたとしても油断してはいけない。現実的な解がえられているか見極める必要がある。
    • ただ、ひとまず最適解がえられていれば、それをもとに結果がおかしくないか検証して、抜けている制約をあぶり出したりできるのでうれしい。

梅谷先生の資料のように、モデルはイテレーションを回しながら作り上げていくのだ。

6.2 Economic interpretations

ここでは具体例を通じて双対問題の解説をしつつ用語を整理している。

  • reduced costs: 被役費用。最適解近傍で、変数の値を微少量動かしたときに、最適解の値がどれくらいかわるか
  • shadow price: 制約を微少量動かしたときに、最適解がどれくらいかわるか

双対問題や双対変数に具体的な解釈を与えるのはいいが、一般性があるわけでもないので、微妙だと思うんだけどどうだろう。 この章はちゃんと理解できているか微妙なので、もう一度読む。

6.3 Sensitivity analysis and the stability of a model

6.3.1 Right-hand side ranges

いわゆる感度分析。制約を動かした時、一定の範囲内であれば、 shadow price にしたがって最適値が変化する。 一方、一定の範囲を超えてしまうと、それが成り立たなくなる。

なぜかといえば、下図のように有効な制約が変わるから。LPは一般的に複数の制約の交点が解になっている。制約を徐々に動かしていく(例えば図のABをA'B'に動かすイメージ)と、その制約の組が変わる(図のDやCEに到達する)ことがあって、それ以降は shadow price に従わなくなる。

f:id:ohtaman:20200718052140p:plain
shadow price が有効な範囲

6.3.2 Objective ranges

制約ではなくて目的関数にあらわれる係数をかえるとどうなるか、という話。下図でいうと、目的関数の等高線PQの傾きを変える。ただ、具体的な応用例があまりイメージできなかった。予測値とかを使っていてブレる可能性がある場合にどれくらい安定的かとか考えるときに使うのかな?

f:id:ohtaman:20200718052856p:plain

6.3.3 Ranges on interior coefficients

もちろん制約式の中の係数も変化できるけど、それほど有用ではないっぽい。ほんとかな。

6.3.4 marginal rates of substitution

制約を動かしたときに、変数がどう動くかを見るのも重要。ちょっとややこしいので、輪読会の中でもこんがらがっていたので整理。

考えるのは以下のLPで、式(6.45)の右辺 4 を少し動かしたときに、最適解の  x _ 1 x _ 2 はどう変化するか。

f:id:ohtaman:20200718055714p:plain

この問題の実行可能領域は下図の通りになっていて、式(6.45)を変化させるのは、(0,4) と A を結ぶ直線を動かすことに対応している。

f:id:ohtaman:20200718055948p:plain

最適解は A なので、  x _ 1 x _ 2 がどう変化するかというのは、 つまりA がどう動くかというはなしで、この場合は 式(6.46)の表す直線( 図でいうと A と (2, 1) を結ぶ直線)の上を動くことになる。具体的には、 x _ 1 が -1 だけ動いて  x _ 2 が +2 動くことになる。

これは marginal rates of substitution と呼ばれる量らしい。現実問題だと、例えばある原材料の供給量が増えたり減ったりしたときに、製造計画をどう変えるべきか、という話に対応するので、とても重要。

6.3.5

結局、現実的な問題だと、最適な解よりも(状況の変化に対して)安定な解が求められることが多い。そうですよね。

TODO

  • 宿題: 12.15

機械学習系の国際会議に参加したい

機械学習系の国際会議

COVID-19 の影響でいろいろなイベントがオンライン化していています。 しかもオンライン化に伴い参加費も抑えられていることが多く、いままでなかなか参加できなかった機械学習系の国際会議にも簡単に参加できるようになっているので、せっかくなのでまとめてみました。

各会議の特徴は こちらのQiita記事 とかが参考になるかと思います。

Conference Shchedule Pricing (for non students)
ACL JUL 5-10 $175
COLT JUL 9 - 12 $50
ICML JUL 12 - 18 $100
KDD AUG 23 - 27 〜 8/14 $200 - $250
8/15〜 $250 - $300
RecSys SEP 22 - 26
EMNLP NOV 16 - 20
NeurIPS DEC 5 - 12
IJCAI JAN 2021
AAAI FEB 2021
ICLR MAY 4 - 8 2021
CVPR JUN 21 - 24 2021

Model Building in Mathematical Programming: 12.19 Distribution 1

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

宿題

12.19 Distribution 1

5章でLPとネットワークの関係について学んだので、その典型的な応用である配送問題。

問題文の解釈に困るところがあったけど、まぁ典型的な問題だった。制約をちょっと緩めた時の目的関数の値の変化が、ちゃんと shadow price と呼ばれる量 (pulp だと、制約式の pi 属性) と対応していることを確かめたりした。

あと、わりとどうでもいい気もするけど、pd.DataFrame.applymap を使って制約を一挙に追加する術を身につけた。pulpの変数を値に持つDataFrameを作ってやって、下記のような感じで制約を追加していく。

df.applymap(lambda x: problem.addConstraint(x == 0))

また、applymapの戻り値はDataFrameなので、これを使って結果を表示するととてもわかりやすい。

f:id:ohtaman:20200701175753p:plain

僕の答案は以下のリンクの通り(輪読会のあとでやった)

colab.research.google.com

Model Building in Mathematical Programming: 5.3 Network models

Optimization NightH. 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

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

Model Building in Mathematical Programming: 5.1〜5.2

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

宿題 (12.24 Yield Management)

普通、航空機の座席の料金はファースト、ビジネス、エコノミーといた座席のクラスだけではなくて、購入時期にも依って変わります。出発がまだまだ先の場合は、そこそこの値段、少し近づいてくるとちょっと安くなって、直前になると高くなる、みたいなのはなんとなく知られていると思います。

今回の宿題では、この航空機の座席の値段を最適化しましょう、というのがお題でした。具体的には3週間後に出発する飛行機について、1週間ごとに座席の値段を調整できて、座席の値段によって需要が変わる場合に、どうすると利益を最大化できるか、という問題です。これを、複数のシナリオ(需要の予測値)があるとして、確率計画法で解きます。

設定が結構複雑なので、アドバイスにしたがって、はじめにいろいろな要件を無視して簡略化したモデルを定式化して、それを修正していく形で解きました。それもあって、書籍の解答例の定式化とは結構違ったものになったと思う。あとで比較してみよう。

それ以外に思ったのは、

  1. 確率計画法だと、すべての可能性を列挙しないといけないので、変数が爆発的に増えて計算がしんどくなる。と思ったけど、今回の例に関して言えば、そうでもない。今回は結局、確率計画法で列挙しなければいけないのが需要変数だけで、かつシナリオの数も3つ(正確には3つ x 期間 x 座席クラス x 取れる価格付けのオプション数)だったから。
  2. 設定が複雑になると、定式化が正しいか、制約はあらいだされているか、を確認するのが難しい。 そのため実案件では、クライアントに提示しては「なんとなく感覚とあわないなぁ」を繰り返す。だからこそ、はじめは汎用ソルバーを使って、とにかく修正を簡単にしておくのが大事。
  3. 予測値がどれくらい外れると、どれくらい最適化に影響するのか調べてみよう。

自分の解答は以下の通り。最後のまではやっていない。

colab.research.google.com

Chapter 5

5.1 Typical applications

線型計画法(というか数理計画法)の応用事例がまとまっている。これは知っておいたほうが良い。資源配分問題はほぼすべての業種で使われていて、それ以外には以下のような事例がある。これも後で具体例と紐づけて、ちゃんと整理しよう。

  1. 石油産業
    • 混合、販売など
  2. 化学産業
  3. 製造業
  4. 運輸業
    • 配送、積み替え、施設配置など
  5. 経理財務
  6. 農業
    • 混合、配送、価格最適化など
  7. 医療
    • スケジューリング、腫瘍への放射線の照射量など
  8. 鉱業
  9. マンパワー計画
  10. 食品エネルギー
    • 結構使われているらしい。
  11. 製紙産業
    • 祭壇ロスの最小化、古紙のリサイクルなど
  12. 広告業
    • 予算配分、メディアスケジューリングなど
  13. 軍事
    • ミサイル基地の配置など
  14. サプライチェーン
    • もろもろ。複数の要素が組み合わさっているので、個々で最適化しようとすると、うまく行かないケースがあるので注意が必要らしい。

教科書が古いので、最近の事例を知りたいという話をしてみたが、そんなに変わっていないらしい(実際には 5th Edition なので最近の事例も追加されている)。昔から結構色んな分野で話があるのに、社会実装が進んでいないという話を聞いてしみじみした。

5.2 Economic models

(正直な話をすると、前日ほぼ徹夜だったため、頭が働かなくなってしまったので、話がちゃんとはいってこなくって、あとで読み直した)

Input-Output モデルと呼ばれるモデルについての紹介。Leontief model とも呼ばれる。複数の産業が絡み合いかたを、それぞれの産業のInputとOutputという形で表現して、その関係性を調べる。例えば、

  1. 各産業でどれくらい生産すると、外需を満たせるか
  2. どれくらい労働力が必要化
  3. 各Outputは、いくらの価値があるか

などを線形計画法をつかって導き出す。最適化したい、というよりは、上記のような課題に合わせて、目的関数を選ぶようなイメージ。

例題は3個の産業だけで成り立っている仮想的な国だったが、実際の国の産業の数(要は、解きたい問題に応じて、同じ性質を持っているものを適当な粒度にまとめたもの)は半端ない。過去の例では、1000固程度までまとめて解析したことがあるらしいが、この1000個というのが(本書ではとても少ないと書かれているが)少ないのかどうか、感覚がなさすぎて、よくわからなかった。

産業がたかだか1000個であれば、簡単に解けそうに思えるかもしれないが、普通の線型計画法の問題と違って、出てくる行列がかなり密(50%くらい非ゼロだったりするらしい)なので、計算時間は結構かかるとのこと。

うちの会社は大きく3つないし4つの事業の組み合わせになっているので、これを使ってなにかしら分析できないだろうか、とか考えたりした。

TODO

  1. Chapter 5 の続きを読む
  2. 宿題(12.24 Yield Management)のコードの整理
  3. 事例の整理
  4. 前回考えていた「双対を知らないでも図形で列生成法を理解する」ができないか引き続き考える

結構やること多い。