Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Model Building in Mathematical Programming #1
Search
Shuhei Fujiwara
April 26, 2020
Technology
0
67
Model Building in Mathematical Programming #1
Shuhei Fujiwara
April 26, 2020
Tweet
Share
More Decks by Shuhei Fujiwara
See All by Shuhei Fujiwara
Model Building in Mathematical Programming #2
shuheif
0
46
Nesterov #2
shuheif
0
64
TensorFlow Docs Translation Proofreading
shuheif
0
810
Nesterov
shuheif
2
140
tbf07-seat-optim.pdf
shuheif
1
9.4k
AdaNet
shuheif
1
360
Google Cloud Next Extended 2019 ML Day
shuheif
4
1.1k
TensorFlow Docs Translation JA
shuheif
1
920
TensorFlow DevSummit 2019 Recap
shuheif
0
700
Other Decks in Technology
See All in Technology
AI長期記憶システム構築のための LLMマルチエージェントの取り組み / Awarefy-LLM-Multi-Agent
iktakahiro
2
250
VPC間の接続方法を整理してみた #自治体クラウド勉強会
non97
1
1k
オーティファイ会社紹介資料 / Autify Company Deck
autifyhq
9
120k
【若手エンジニア応援LT会】AWS Security Hubの活用に苦労した話
kazushi_ohata
0
250
今、始める、第一歩。 / Your first step
yahonda
2
470
ZOZOTOWNのホーム画面をパーソナライズすることの難しさと裏話を語る
f6wbl6
1
290
AI機能の開発運用のリアルと今後のリアル
akiroom
0
170
全社横断データ活用推進のコツと その負債とのつき合い方
masatoshi0205
0
120
株式会社ログラス − エンジニア向け会社説明資料 / Loglass Comapany Deck for Engineer
loglass2019
3
28k
SREの組織類型に応じた リーダシップの考察
kenta_hi
PRO
0
400
10分でわかるfreeeのQA
freee
1
3.4k
プロポーザルのつくり方 〜個人技編〜 / How to come up with proposals
ohbarye
4
280
Featured
See All Featured
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
92
16k
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
Fashionably flexible responsive web design (full day workshop)
malarkey
404
65k
Art, The Web, and Tiny UX
lynnandtonic
297
20k
BBQ
matthewcrist
85
9.3k
How to Ace a Technical Interview
jacobian
275
23k
Happy Clients
brianwarren
97
6.7k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
505
140k
The Art of Programming - Codeland 2020
erikaheidi
52
13k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
Practical Orchestrator
shlominoach
186
10k
The Language of Interfaces
destraynor
154
24k
Transcript
Model Building in Mathematical Programming #1 @shuhei_fujiwara
今日の範囲 Chapter 1 • 線形計画の簡単な例 Chapter 2 • 最適化のパッケージ(ソフトウェア)に関する話など Part
2: Section 12.1 • Chapter 1 の例に近い問題
Chapter 1
Section 1.1: The concept of a model 読み物なのでほぼ skip •
“model” という言葉の使い方について ◦ 最適化の文脈では抽象的な定式化などを指す • モデルを作る利点について ◦ 分析や意思決定だけでなく課題への理解が深まる利点もある など
Example 1.1: Product Mix Product 1~5 を生産すると得られる利益: 各 product の生産に必要な工程:
PROD 1 PROD 2 PROD 3 PROD 4 PROD 5 £550 £600 £350 £400 £200 PROD 1 PROD 2 PROD 3 PROD 4 PROD 5 Grinding 12 20 - 25 15 Drilling 10 8 16 - -
Objective function x1 ~ x5: product 1 ~ 5 の生産量
max 550 x1 + 600 x2 + 350 x3 + 400 x4 + 200 x5 • 利益 × 生産量 の総和 • いくつかの制約下でこれを最大化するのが目標
Constraints: grinding, drilling 12 x1 + 20 x2 + 25
x4 + 15 x5 ≦ 288 • Grinding 作業の機械が 1 週間に 96 時間まで稼働できる ◦ 今回は 3 週間の計画なので 96 × 3 = 288 が上限 10 x1 + 8 x2 + 16 x3 ≦ 192 • 同様に Drilling の機械は 192 時間まで稼働できる
Constraints: assembly, not negative quantities 20 x1 + 20 x2
+ 20 x3 + 20 x4 + 20 x5 ≦ 384 • Product 共通の最終組み立て工程があって 20 時間かかる • この機械は 8 台あって 48 時間ずつ稼働できる ◦ 合計で 48 × 8 = 384 時間 x1, x2, x3, x4, x5 ≧ 0 • 当たり前だが各 product の生産量は負の値にはできない
Formulation 以下を達成する x1 ~ x5 を求めれば良い: max 550 x1 +
600 x2 + 350 x3 + 400 x4 + 200 x5 s.t. 12 x1 + 20 x2 + 25 x4 + 15 x5 ≦ 288 10 x1 + 8 x2 + 16 x3 ≦ 192 20 x1 + 20 x2 + 20 x3 + 20 x4 + 20 x5 ≦ 384 x1, x2, x3, x4, x5 ≧ 0
補足 • 今回の例は目的関数も制約も全て線形 ◦ Linear Programming (LP) というクラスの問題 ◦ 制約は
≦ だけでなく ≦ や = を使って定義しても良い • 変数 x1 ~ x5 は 2.36 のような整数以外の値でも大丈夫? ◦ ビールを何ガロン生産するかみたいな問題なら OK ◦ 車を何台生産するかというような問題だとマズい ◦ 変数 x1 ~ x5 が整数の場合は Integer Programmin (IP)
Example 1.2: Blending 次の表の油を混ぜて作った商品を販売したい: • 1 トンあたり £150 で販売する •
混ぜると硬度は線形に変化する ◦ VEG 1 と OIL 3 を半々で混ぜると 0.5 × 8.8 + 0.5 × 5 = 0.69 ◦ 低すぎても高すぎても良くない VEG 1 VEG 2 OIL 1 OIL 2 OIL 3 Cost £110 £120 £130 £110 £115 Hardness 8.8 6.1 2.0 4.2 5.0
Objective function x1 ~ x5: VEG 1 ~2, OIL 1
~ 3 の生産量 y: 混ぜて作った油の量 max 150 y - 110 x1 - 120 x2 - 130 x3 - 110 x4 - 115 x5 s.t. y = x1 + x2 + x3 + x4 + x5
Constraints: hardness 8.8 x1 + 6.1 x2 + 2 x3
+ 4.2 x4 + 5 x5 ≦ 6 y 8.8 x1 + 6.1 x2 + 2 x3 + 4.2 x4 + 5 x5 ≧ 3 y • 最終的な硬度は 3 ~ 6 でなければならない
Constraints: capacities x1 + x2 ≦ 200 x3 + x4
+ x5 ≦ 250 • VEG は合わせて 200 までしか生産できない • OIL は合わせて 250 までしか生産できない
Formulation max 150 y - 110 x1 - 120 x2
- 130 x3 - 110 x4 - 115 x5 s.t. y = x1 + x2 + x3 + x4 + x5 x1 + x2 ≦ 200 x3 + x4 + x5 ≦ 250 8.8 x1 + 6.1 x2 + 2 x3 + 4.2 x4 + 5 x5 ≦ 6 y 8.8 x1 + 6.1 x2 + 2 x3 + 4.2 x4 + 5 x5 ≧ 3 y x1, x2, x3, x4, x5 ≧ 0
まとめ • 色々な問題を Linear Programming (LP) として表現することができる ◦ LP はコンピュータで効率的に解けることが知られている
• 変数が整数値という制約が付くものは Integer Programming (IP) ◦ IP は LP と比べて非常に難しい ◦ Chapter 8 ~ 10 で紹介 • 線形でないものは Non-Linear Programming (NLP) ◦ これは Chapter 7 で紹介
Chapter 2
2.1 Algorithms and packages 最適化では解決したい課題を LP のような問題に落とし、実際にその解を求める部分は 既存のソフトウェア (packages) に任せるのが王道
• 既存のソフトウェアは非常に時間をかけて作り込まれており高機能 • 自前で実装するのは大変 この section ではよくある機能の例を紹介
Reduction • 問題を解く前に冗長な部分を削除してくれる • REDUCE, PRESOLVE, ANALYSE といった名前の機能 • 詳しくは
section 3.4
Starting solutions • 初期解を与えることができる • 最適解に近いものを渡せば計算時間を大幅に 減らすことができる
Constraints いくつかの単純な制約は簡単に書けるように設計されている Simple bounding constraints: • L ≦ x ≦
U Ranged constraints: • Σ aj xj ≦ b1 and Σ aj xj ≧ b2 Generalized upper bounding constraints: • x1 + x2 + … + xn ≦ M
Sensitivity analysis • 目的関数や制約式の定数などが変わったときに 解がどう変化するかを分析することができる • 感度分析という有名な話で詳しくは Section 6.3
2.2 Practical considerations ちょっとした tips など • 入力の形式の例 • 結果を保存する機能を活用すると良い
◦ 少し数値を変えた問題を解く時の初期解として有用 ◦ 途中で計算を止めて再開したいケースもある
2.3 Decision support and expert systems • 最適化の応用は decision support
system や expert system と近い • ユーザーにはアルゴリズムやモデリングを意識させること無く 適切な意思決定をできるようなインターフェースも重要
Constraint programming (CP) IP とは別に制約充足問題という文脈で研究されている手法もある • 解きたい問題はだいたい同じだったりする • IP の流儀とは制約の表現の仕方が違ったりする
• CP の流儀の方がきれいに書き表せるケースも有る 開発されているアルゴリズムにも差がある • CP の方が少ない実行可能解を見つけるのは得意だが、巡回セールスマン問題の ような大量の実行可能解から最適なものを見つけるのは苦手
Chapter 12
12.1: Food manufacture 1 • 次回までの宿題 ◦ 時間が余ったら今日議論 • Example
1.2 と同じような問題設定