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
68
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
65
TensorFlow Docs Translation Proofreading
shuheif
0
810
Nesterov
shuheif
2
140
tbf07-seat-optim.pdf
shuheif
1
9.4k
AdaNet
shuheif
1
370
Google Cloud Next Extended 2019 ML Day
shuheif
4
1.1k
TensorFlow Docs Translation JA
shuheif
1
920
TensorFlow DevSummit 2019 Recap
shuheif
0
710
Other Decks in Technology
See All in Technology
SREが投資するAIOps ~ペアーズにおけるLLM for Developerへの取り組み~
takumiogawa
2
470
テストコード品質を高めるためにMutation Testingライブラリ・Strykerを実戦導入してみた話
ysknsid25
7
2.7k
The Rise of LLMOps
asei
9
1.7k
Engineer Career Talk
lycorp_recruit_jp
0
190
オープンソースAIとは何か? --「オープンソースAIの定義 v1.0」詳細解説
shujisado
10
1.3k
FlutterアプリにおけるSLI/SLOを用いたユーザー体験の可視化と計測基盤構築
ostk0069
0
110
Introduction to Works of ML Engineer in LY Corporation
lycorp_recruit_jp
0
140
New Relicを活用したSREの最初のステップ / NRUG OKINAWA VOL.3
isaoshimizu
3
640
Flutterによる 効率的なAndroid・iOS・Webアプリケーション開発の事例
recruitengineers
PRO
0
120
【Startup CTO of the Year 2024 / Audience Award】アセンド取締役CTO 丹羽健
niwatakeru
0
1.3k
Lexical Analysis
shigashiyama
1
150
[CV勉強会@関東 ECCV2024 読み会] オンラインマッピング x トラッキング MapTracker: Tracking with Strided Memory Fusion for Consistent Vector HD Mapping (Chen+, ECCV24)
abemii
0
230
Featured
See All Featured
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
250
21k
Intergalactic Javascript Robots from Outer Space
tanoku
269
27k
Measuring & Analyzing Core Web Vitals
bluesmoon
4
130
Building Applications with DynamoDB
mza
90
6.1k
Large-scale JavaScript Application Architecture
addyosmani
510
110k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
How GitHub (no longer) Works
holman
310
140k
Being A Developer After 40
akosma
87
590k
Scaling GitHub
holman
458
140k
Teambox: Starting and Learning
jrom
133
8.8k
Art, The Web, and Tiny UX
lynnandtonic
297
20k
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 と同じような問題設定