0-8

Model Building in Mathematical Programming: 12.19 Distribution 1

数理最適化

Optimization Night で H. 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 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

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

Model Building in Mathematical Programming: 5.1〜5.2

数理最適化

Optimization Night で H. 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. 前回考えていた「双対を知らないでも図形で列生成法を理解する」ができないか引き続き考える

結構やること多い。

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) がある。

不確実なデータの取りうる値が離散化できる場合は、以下のようにする。

  1. 可能性のある値それぞれに対応する変数をすべて用意する。
  2. 上記の変数に確率値を掛け算することで、期待値としたものを目的関数に用いる

ただし、多期間問題のような状況では、考える期間の指数オーダーで変数が増えるので注意が必要。

ロバスト最適化と呼ばれる方法とも関係があるが、ロバスト最適化の場合は、データの不確実性に対する解の安定性を評価することが多く、この方法は不確実性が定量化できなかったとしても適用可能。 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 分解の方。

いわゆる列生成法と呼ばれる手法（列生成法についてはこちらの資料がわかりやすい）。マルチプラントモデルを例にとれば、全体で最適な生産計画を練ろうとすると、

  1. 各プラントにどれだけの原材料を配分して、
  2. 各プラントで何をどれだけ作るかを決める

必要がある。 逆に言うと、この2つの問題を解けば、全体で最適な生産計画が得られることになる。 1. のことを主問題、2. のことを子問題と呼ぶ。Dantzig-Wolfe分解では、主問題で原材料の配分割合を直接指定する代わりに、原材料の価格(internal price) という変数を定義して、ちょうどいい配分になるような価格を探る問題として解く。

この辺の話は双対問題で考えると考えやすい（実際、前述の列生成法の資料でも双対問題を解いている）と思うけど、この本ではそういった話はしていなかったのもあり、著者の思惑をきちんと理解できたかはかなりあやしい。なんとか直感的に理解したいものだが。。

分散計画経済の話が出てきたが、きちんと理解できていない。ただ、米国の電力会社などでそれに似た事例が報告されているらしい。

日本でも米国でも、事例を集めるのはとても有意義な気がするので、やってみよう。

今回も自分が発表担当したので、当日の発表資料 も合わせてご覧ください。

TODO

  1. 宿題: 12.24 Yield management を解く
  2. Chapter 5 を読む
  3. Dantzig-Wolfe分解について、双対の概念なしに、図形的に理解できないか、もうちょっと頑張ってみる。

Model Building in Mathematical Programming: 4.1

数理最適化

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

宿題（12.22 Efficiency Analysis）

いわゆる DEA (Data Envelopment Analysis, 包絡分析) の問題。自動車メーカーが複数のガレージとフランチャイズ契約を結んでいる設定で、各ガレージの効率を評価する.

DEA の概念は知っていたが、具体的な使いかたや解放は知らなかったので、勉強になった。 宿題を解く上で参考にさせてもらった こちらの解説記事 はとてもわかり易かったのでおすすめ。

DEA では、入力（店舗の広さやスタッフ数等）と出力（売上や利益等）の比 (出力 ÷ 入力) を効率値として評価する。 入力や出力が複数ある場合は、各ガレージが最も有利になるような重みで足し合わせて効率を計算するので、画一的な評価にならず、個性のあるガレージをちゃんと評価に反映できる。人事評価にも応用できるのでは？という意見も出たが、突拍子もない施策をおこなうことで、すきなだけ効率値を挙げられてしまうという問題もあり、なかなか一筋縄ではいかなさそう。

あとは、入力や出力をどのように選択するのか、という問題もある。EDAでは、最も効率のよい店舗の効率値が1となるような正規化をしているが、入出力の数が多いと、自由度が高すぎて、ほとんどの店舗の効率値が1なんて状況にもなりかねない。また、ある出力と関係のない指標を入力にいれてしまうと、なにを見ているのかわからなくなってしまう。このあたりの議論をしていたときに、産業連関表 というキーワードがでてきた（全く理解していない）。産業連関表の用途や使い方については こちらのOR学会の記事 が参考になるみたいなので、あとで読んでみる。

自分の答案は以下のとおり colab.research.google.com

Chapter 3

3.1 The importance of linearity

例えばマルチプラント（工場が複数あって、全体の利益や売上を最大化するような問題）だと、各プラント内での最適化と、プラント間での最適化の両方を同時に解く必要がある。こういった問題を定式化すると、各プラント内で閉じている部分と、プラント間にまたがる部分（例えば物品のやり取りや割当に関する制約）が出てくる。問題にこういった構造が入っていると、解きやすくなることがある（具体的な話は 4.2 以降）。

ちなみにこの本では、制約がブロック対角な部分と共通の行だけで構成される構造をブロック対角構造、ブロック対角ではないが多期間問題で今月と次月だけがかぶっているような構造を階段構造（実際にはブロック対角構造に書き直せる）と読んでいる。ブロック対角な部分と共通の列だけで構成される構造も紹介されていたが、呼び名を与えられていなかったのでかわいそうだった。

今回は自分が発表担当したので、当日の発表資料 も合わせてご覧ください。

Model Building in Mathematical Programming: 3.2.4〜3.5

数理最適化

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

Chapter 3

3.2 Defining objectives （続き）

引き続き、目的関数について語る。

3.2.4 Ratio objectives

パフォーマンスや効率を評価するときに出てくる以下のような目的関数は、線型に書き直すことができる。DEA（包絡分析）ですね。

\frac{\sum_{j}a_jx_j}{\sum_j b_j x_j}

3.2.5 Non-existent and non-optimizable objectives

制約を満たす解がほしいだけで、最適解である必要がない場合は、目的関数なし、なんていうのもある。最近のソルバーは、目的関数なしでも動くらしい。制約を満たす「極端な」解を得ることもできるので、デバッグに有用という話は面白かった。

3.3 Defining constraints

これ以降は制約の話。各章の抽象度があっていない気がした。

  1. Productive capacity constraints
    • 生産能力に関する制約
  2. Raw material availabilities
    • 原材料の利用可能性に関する制約
  3. Marketing demands and limitations
    • 生産量に関する、需要やその他の要請から生まれる制約
  4. Material balance (continuity) constraints
    • 質量保存などの制約
  5. Quality stipulation
    • 原材料を混合する際の混合割合など、品質規定などから要求される制約

3.3.6 Hard and soft constraints

制約は実際には必ずしも制約ではない。そこで、絶対に満たさないといけない制約をHardな制約、満たさないといけないけど、場合によっては満たさなくても...みたいなものはSoftな制約と呼ぶ。 制約とはいったい。。数理最適化って、こういう学問的というよりは現実問題に目を向けているあたりが好きだったりもする。

違反量を表す変数を導入して、目的関数でペナルティをかけるのが単純な方法だが、ファジー最適化といった手法もある。そしてファジー最適化は定式化を変えることでLP問題に帰着できる。ふむふむ。

3.3.7 Chance constraints

ある一定の確率以上で制約を満たしなさい、という制約。手元の本では機会制約と訳してあった。確率的最適化手法の一種。

3.3.8 Conflicting constraints

制約同士が矛盾してしまう場合に、「できるだけ制約を満たす解を探せ」という問題になることもあって、それは Goal Programming と呼ばれている。

目的関数をどうやって設定するかというと、2種類の方法があって、後者は多少複雑だが、LPで定式化できる。

  1. 違反量の重み付き総和を最小にする
  2. 最大の違反量を最小にする

3.3.9 Redundant constraints

潜在価格 (shadow price) は、制約を少し緩めたときの、最適解への影響具合。潜在価格がゼロな制約は、最適解に影響を与えないため冗長と言える。でもデータが変わったりして冗長でなくなることもあるし、安易に取り除いてはだめ。

3.3.10 Simple and generalized upper bounds

変数の上下限や、Generalized upper bounds は、ソルバにとって有用なので、それを定義するメソッドがある場合は使ったほうが良さげ。

3.4 How to build a good model

  1. 理解しやすい定式化をしよう
    • 前回も出てきたが、補助的な変数をつかっても計算量的にはそこまで問題にならない
      • 最近のソルバは解釈性を解析してレポートしてくれる機能もあるもよう
    • わかりやすい変数名をつけよう
  2. エラーを検出しやすいように記述しよう
    • Typoとか定式化の間違い。大概の場合PRESOLVEするとunboundedとかinfeasibleになるので検出できる（ほんまかいな）
    • 数理最適化問題の、エラーにハマりにくい書き方どこかにまとまってないかな。
  3. Modal formulation というテクニックがあるが、あまり使われていない模様。なので僕は調べない。
  4. 変数の単位を揃えよう

3.5 The use of modeling language

古い本だからね〜、当時は確かにいろいろ問題があったから、modeling language をおすすめしたのはわかるけど、今は pulp かければいいんじゃない？的な話になった。

TODO

  1. 宿題（12.22 Efficiency analysis）を解く
  2. Chapter 4 を読む
    • 担当自分だ。間に合う気がしない。

Model Building in Mathematical Programming: Chapter 3 〜 3.2.3

数理最適化

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

宿題（12.1 Food manufacture 1）

はじめの1時間は宿題（12.1 Food manufacture 1）の答え合わせと議論になった。 僕の答案はColaboratoryで共有。 はじめ一部の条件の解釈を間違えていたけど、それ以外はだいたい正しそう（Colaboratoryは修正済）。

典型的な線形計画問題なので、英語の解釈を除いて定式化に悩むことはなかったが、補助変数を追加することの是非について議論になった。今回の例だと、

月末の在庫 = 初期在庫 + その月までの購入量 - その月までの使用量

となるが、「月末の在庫」にあえて変数を割り当てるかどうか。要は、等式制約しか入っておらず事前に展開することが可能なので、あえて「月末の在庫」変数を作る必要はないのではないか、という話。こういった補助変数を追加したほうが式の見た目がスッキリして解釈しやすくなるし、バグの混入も減らせる。では、計算量という観点で変数が増えるのは問題ないのかというと、あまり問題にならないことが多そう。ソルバー的には補助変数にまとめられているものをバラすのは簡単だが、あらかじめバラしてしまったものをまとめるのは難しい。なので、もちろん場合によるが、まずは変数の数が増えるとかはあまり気にせずに補助変数を追加しておけば良さそう。

Chapter 3

3.1 The importance of linearity

線形計画問題（目的関数も制約も線形な数理計画問題）は、他の問題に比べて解くのが簡単なので重要。もちろん、現実的な問題では、それでは間に合わないことも多いけど、非線形な問題の近似になるので、やっぱり重要。

3.2 Defining objectives

よく出てくる目的関数一覧

  • 利益（最大化）
  • コスト（最小化）
  • 効用（最大化）
  • 売上（最大化）
  • ROI（最大化）
  • NPV（最大化）
  • 従業員数（最大化・最小化）
  • 余剰（最小化）
  • 顧客満足度（最大化）
  • 生存確率（最大化）
  • 堅牢性（最大化）

3.2.1 Single objectives

よく出てくる目的関数として「利益」や「コスト」を挙げたが、正確には「利益への貢献」、「変動コスト」とすべき。というのも、線型計画問題の場合は変数が連続量のみなので、固定コストは最適化できないので。これはなるほどなと思った。

あと、利益を最大化する問題では、製品 i 1単位あたりの貢献利益を P _ i 、需要を d _ i とすると、利益は P _ i d _ i で表せるが、単価が需要によって影響を受けるような場合、 P _i が定数でないため、目的関数が線形でなくなってしまうので注意が必要。

3.2.2 Multiple Objective

多目的最適化（複数の目的関数を同時に最適化）の方法は、大別して以下の3つがある。

  1. 目的関数を個別に最適化する
    • それぞれの目的関数を使って最適化問題を解き、結果を比較する
  2. 目的関数を制約に変換する
    • 1つだけ残して、後は制約として取り入れる
  3. 目的関数の線形和を最適化する
    • 重みの調整が大変で、経験的には、目的関数が3つか4つくらいまでは、勘がよければうまくいくことがあるらしい。データが大きく変わると重みも調整しないといけなくなるので、似たようなデータが来ることがわかっているような状況では良いかも、というコメントがあって、これもなるほどなと思った。
    • 受託分析をしている立場から言うと、良い悪いはおいておいて「顧客に調整できる余地を残しておく」というのは重要だったりするので、そういう観点では他の2つよりも使い勝手は良いのかもしれない。

多目的最適化については、以下の Minimax を使うことが多いという意見も出た。例えば Optimization Night の梅谷先生の資料の電子ジャーナル購読では、各雑誌それぞれについて、充足率を最大化したいところを、最小充足率の最大化として定式化している。

3.3.3 Minimax Objectives

Minimax（ある値を最大値を最小化する）問題は、最大化したいものの上限を表す変数 z を導入すれば、（最大化したい値が z以下であるという）線形な制約をもった最小化問題になる。一方で、Maximax問題は線形計画問題に帰着できず整数計画問題となるということが書かれていたが、そもそも Maximax 問題がどういうものなのかすらイメージできなかった。

TODO

  • Chapter 3、 Chapter 4 を読む