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分解について、双対の概念なしに、図形的に理解できないか、もうちょっと頑張ってみる。
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(包絡分析)ですね。
3.2.5 Non-existent and non-optimizable objectives
制約を満たす解がほしいだけで、最適解である必要がない場合は、目的関数なし、なんていうのもある。最近のソルバーは、目的関数なしでも動くらしい。制約を満たす「極端な」解を得ることもできるので、デバッグに有用という話は面白かった。
3.3 Defining constraints
これ以降は制約の話。各章の抽象度があっていない気がした。
- Productive capacity constraints
- 生産能力に関する制約
- Raw material availabilities
- 原材料の利用可能性に関する制約
- Marketing demands and limitations
- 生産量に関する、需要やその他の要請から生まれる制約
- Material balance (continuity) constraints
- 質量保存などの制約
- 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で定式化できる。
- 違反量の重み付き総和を最小にする
- 最大の違反量を最小にする
- ボトルネック問題と呼ばれている
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
- 理解しやすい定式化をしよう
- 前回も出てきたが、補助的な変数をつかっても計算量的にはそこまで問題にならない
- 最近のソルバは解釈性を解析してレポートしてくれる機能もあるもよう
- わかりやすい変数名をつけよう
- 前回も出てきたが、補助的な変数をつかっても計算量的にはそこまで問題にならない
- エラーを検出しやすいように記述しよう
- Modal formulation というテクニックがあるが、あまり使われていない模様。なので僕は調べない。
- 変数の単位を揃えよう
3.5 The use of modeling language
古い本だからね〜、当時は確かにいろいろ問題があったから、modeling language をおすすめしたのはわかるけど、今は pulp かければいいんじゃない?的な話になった。
TODO
- 宿題(12.22 Efficiency analysis)を解く
- 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
よく出てくる目的関数として「利益」や「コスト」を挙げたが、正確には「利益への貢献」、「変動コスト」とすべき。というのも、線型計画問題の場合は変数が連続量のみなので、固定コストは最適化できないので。これはなるほどなと思った。
あと、利益を最大化する問題では、製品 1単位あたりの貢献利益を 、需要を とすると、利益は で表せるが、単価が需要によって影響を受けるような場合、 が定数でないため、目的関数が線形でなくなってしまうので注意が必要。
3.2.2 Multiple Objective
多目的最適化(複数の目的関数を同時に最適化)の方法は、大別して以下の3つがある。
- 目的関数を個別に最適化する
- それぞれの目的関数を使って最適化問題を解き、結果を比較する
- 目的関数を制約に変換する
- 1つだけ残して、後は制約として取り入れる
- 目的関数の線形和を最適化する
- 重みの調整が大変で、経験的には、目的関数が3つか4つくらいまでは、勘がよければうまくいくことがあるらしい。データが大きく変わると重みも調整しないといけなくなるので、似たようなデータが来ることがわかっているような状況では良いかも、というコメントがあって、これもなるほどなと思った。
- 受託分析をしている立場から言うと、良い悪いはおいておいて「顧客に調整できる余地を残しておく」というのは重要だったりするので、そういう観点では他の2つよりも使い勝手は良いのかもしれない。
多目的最適化については、以下の Minimax を使うことが多いという意見も出た。例えば Optimization Night の梅谷先生の資料の電子ジャーナル購読では、各雑誌それぞれについて、充足率を最大化したいところを、最小充足率の最大化として定式化している。
3.3.3 Minimax Objectives
Minimax(ある値を最大値を最小化する)問題は、最大化したいものの上限を表す変数 を導入すれば、(最大化したい値が以下であるという)線形な制約をもった最小化問題になる。一方で、Maximax問題は線形計画問題に帰着できず整数計画問題となるということが書かれていたが、そもそも Maximax 問題がどういうものなのかすらイメージできなかった。
TODO
- Chapter 3、 Chapter 4 を読む
Model Building in Mathematical Programming: Chapter 1, Chapter 2
Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。
Chapter 1
1.1 The concept of a model
ここでは「モデル」という言葉のコンセプトについて議論。数理最適化もしくはオペレーションズ・リサーチの文脈では抽象的な数理モデルを指すことが多い。 機械学習や物理学の文脈でも「モデル」という言葉がでてきて、それぞれなんとなくイメージしている抽象度が違いそうなので、コミュニケーションの際には注意が必要そう。 京都大学のページ にもあるとおり、数理最適化は
- 問題のポイントを整理して数学モデルを作成する.
- モデルの特性を考慮した適切な方法(アルゴリズム)を用いて解を求める.
- 得られた解をもとに現実の問題の解決策を実施する.
というステップを踏むことになるので、「モデル」のコンセプトを理解して「アルゴリズム」と区別するのはとても大事。
あまり本筋とは関係ないですが、 本書ではオペレーションズ・リサーチのことを operations research ではなく operational research と書いてあります。 Wikipedia によると、 operational research はイギリス英語らしい。
Chapter 2
2.1 Algorithms and packages
既存のパッケージ(Gurobiなどのソルバー)は長年の研究の成果を泥臭く実装していて、素人に手を出せるようなものではないので、むやみにアルゴリズムを実装したりせず、既存のパッケージを利用しましょう。昔 cbc (Coin-or branch and cut) という数理最適化ソルバーのコードを読み解こうとしたのを思い出しました。
既存のパッケージの多くは、以下のような典型的な制約を簡単に記述する機能が備わっていて、そういった機能を使うと効率的に計算してくれることがあるので、できるだけ使ったほうが良さそうです。(最近のパッケージでは自動的に判定して効率的な計算をしてくれるものもあるようです。)
- Simple bounding constraints:
- Ranged constraints:
- Generalized upper bounding constraints:
あとは適切な初期解を与えるのも計算時間の短縮に効果的。 また、Sensitivity Analysis (感度分析) についてもふれていて、少し議論ができて楽しかったです。
2.2 Practical considerations
既存のパッケージには、計算結果(途中結果を含む)を保存する機能がついていることが多いので、それを活用しましょう。 数値を少しだけ変えた問題を解く際に初期値として使うこともできるし、計算リソース等の関係で、途中で計算をやめて再開したいケースもある。 コメントもあったけど、このあたりは機械学習周りと感覚が似ている。(というか機械学習がそもそも数理最適化問題の一種なので当然といえば当然かも)
2.4 Constraint programming
ここでは CP (Constraint programming) と IP (Integer Programming)との関係についても触れています。 個人的に CP に興味があるけど全く触ったことがなかったし、イメージもよくわからなかったので、とても助かった。 CPとIPは、もともと別の文脈で発展していて、コミュニティも別だったりするけど、同じ問題を解けたり解けなかったりするので面白い。CPの方が少ない実行可能解を見つけるのは得意だが、巡回セールスマン問題のような大量の実行可能解から最適なものを見つけるのは苦手なんだそうです。また、CPでは、以下のようなglobalな制約を記述できるので、見通しが良くなりそう。(IPとして記述できるけど、変数が増えたり定式化が複雑になったりして大変そう)
-
- がすべて違う値
-
- 普遍と左辺が異なる値
-
- cardinality. ちょうど 個の値が
-
- 時刻 にスタートして の時間と のリソースを消費するジョブが 個あった時に、利用リソースが常に を超えない
-
- が順列になっている
-
- が の 番目の要素と等しい
-
- 集合同士の大小関係 (ある があって、 の場合に true)
TODO
- 12.1 Food manufacture 1 を解く
- 2.1 に出てくる REDUCE, PRESOLVE, ANALYSE がそれぞれ何を指しているのか確認する
イベント盛り上げるのに良いな、と思ったサービス: Kahoot, Sli.do, SwapCard
アメリカの技術イベントに参加して、そこで使われていていいなと思ったサービスをまとめておこうと思います。
Kahoot
Kahoot は、簡単にいうとクイズを簡単につくれるサービスです。スマフォを使ってリアルタイムに出題 > 回答 > 採点(早いほどポイントが高い) > ランキング ができて、けっこう盛り上がります。
単なるクイズプラットフォームではなく、教育にゲーミフィケーションを持ち込むことを目的としていて、学校の授業や企業のオンボーディング用に用いられているようです。教育者観点での使用感はこちらの記事(PDF)にまとまっていますが、学校の授業で盛り上がらないはずはないし、教育的な効果も期待できるし、とても良いサービスな気がします。
ただ、企業のオンボーディングでつかうイメージが正直わかない。大企業だと違うのかな...。リアルタイム性が売りだと思うので、一定以上の人数が同時に入社研修うけたりしないと意味がなさそう。全体会議の最後にコンプライアンステスト、みたいなのは意味がありそう。
Sli.do
Sli.doはこれまでも何回か利用経験があるのですが、聴衆から質問を集めるサービスです。LTとか、時間が決まっていて質問しづらい、会場が広すぎてマイクを持っていくのに時間がかかる、リモート参加の方にも同じ質問機会を与えたい、質問内容を運営側がある程度フィルタリングしたいなど、色々状況で有用なサービスだと思います。
Swapcard
最近のイベントでは、専用のイベントアプリがあって、それを使ってセッションのリザベーションやリマインド、開催会場の確認ができるようになっていることが多いです。Swapcard はイベント & ネットワーキング用のサービスで、開催するイベントの情報の表示や参加者の一覧ができて、イベントアプリを0から作る必要がなくなります。使い勝手は個人的には「まぁ普通」と言ったところでしたが、周りの評判はとても高かったです。常々感じていたのが、イベント毎にアプリインストールするの面倒くさいし、微妙に使い勝手も違うし、ものによっては質も悪いし、なんとかならないかな、ということだったので、こういったサービスを使って、一本化してもらいたいなぁと思いました。
セッションが複数あるような、ある程度大きいイベントでないと意味がない気がするので、直近で自分が利用する機会はなさそうですが。
TensorFlow UserGroup で話す時用のMarpのスライドテーマ を作った
これまでは Google Slides を使うことが多かったのですが、毎回そんなに複雑なことをするわけでもないので、Markdown でお手軽にスライドを作成できるように、 Marpのテーマを作りました。
↓みたいな感じの Markdown を書くと
# Your Name - a - b - c ![your logo](assets/logo.png)
↓みたいなスライドに変換されます。
これでスライド作成がはかどります。
Marp とは
Marpはyhattさんが開発している、 Markdown記法からスライドを生成するアプリ・ライブラリのことです。 もともとはPDFに出力して使うことを想定されていたようですが、現在はHTML出力も可能になっています。CSSを記述することで独自のテーマを適用することもできます。
Markdown記法からスライドを生成する方法は、Marp以外にも色々あって、たとえばreveal.jsが有名だと思います。あと、Qiitaに書くような内容に限るのであれば、Qiitaのスライドモードを使うのが手っ取り早いと思います。 そんな中で、Marpは日本初ながら
- 余計なことをしないので、独自テーマが使いやすい
- Visual Studio Code の拡張機能が使いやすい
- Qiita のようにサービスの制約を受けない / 完全にローカルでプレビューを見ながら執筆できる
- 開発も活発に進んでいる(ように見える)
という点で、とても良い立ち位置にいると思います。
スライドを Markdown で記述するメリット
エンジニアであれば誰でも Markdown は記述できる点、専用の(高価な)ソフトが不要な点、テキストなのでバージョン管理が楽である点などいろいろありますが、個人的には、できることが限られているので、(結果的に)調整に時間が取られないというのが一番のメリットだと思います。
スライドをMarkdown で記述するデメリット
一方で、デメリットもあります。例えば、共同編集には弱い点。共同編集は、Google Docs や Office 365 であれば標準で備えている機能で、複数人で1つのスライドを作り上げていくような場合だと重宝するというか、なくてはならない機能だと思います。Markdownで記述する場合は、Markdownを共同編集できるような環境を別途作らなければいけないというデメリットがあります。 共同編集という意味だと、会社ではエンジニアと営業が協力して1つのスライドを完成させるようなケースも多いと思いますが、正直営業さんに Markdown を強要する勇気は僕にはありません。
また、Markdown でできる範囲は限られているので、その範囲からはずれたことをやろうとすると、とても時間がかかってしまうというのもデメリットかもしれません。(ただ、これは必要以上に作り込まなくなるというメリットと裏表でもありますが...)
ちなみに、Markdown だけの機能だと、ダイアグラムのようなものを記述することはできないのですが、Marpでは、一度HTMLに変換してから必要に応じてPDFに変換しているため、mermaid.js のような、JavaScriptのライブラリを使ってダイアグラムを記述することができます。
執筆環境について一言
Markdown から HTML/PDF への変換方法には、marp-cli というコマンドを利用する方法、Marpをライブラリとしてnodeから呼び出す方法、対応しているエディタの拡張機能を利用する方法などがあります。
普段 Visual Studio Code(vscode) を利用しているのですが、Marp拡張 marp-vscode を入れると、プレビューを確認しながら書きすすめることができるのでとても便利です。
- プレビューが自動更新される
Markdownそのものではなく、適用しているテーマのcssを更新してもプレビューが更新されるので、独自テーマの作成がとてもはかどりました。 - テーマとしてリモートのcssも指定できる
これは marp-cli だとできないように見えますが、今回のようにテーマを公開したい場合にはとても重宝される機能だと思います。
まとめ
Marp と marp-vscode を使って快適なスライドライフをお過ごしください。