【新卒研修資料】数理最適化 / Mathematical Optimization

株式会社ブレインパッドの2025年新卒研修資料です。数理最適化について扱っています

※ 本資料の公開は、ブレインパッドをもっとオープンにする取り組みOpenBPの活動です。
[OpenBrainPad Project]
https://brainpad.github.io/OpenBrainPad/

Transcript

1. 数理最適化研修
2. 2 ©BrainPad Inc. Strictly Confidential 本日のスケジュール タイムライン 所要時間(分)* 内容 9:45-10:15 30 ①数理最適化イントロダクション 10:15-11:10 55 ②線形計画 定式化 11:10-12:00 50 ③線形計画 実装 12:00-13:00 60 昼休憩 13:00-14:00 60 ④整数計画 定式化&実装 14:00-15:00 60 ⑤混合整数計画 定式化&実装 15:00-16:40 100 ⑥実践演習 16:40:17:40 60 ⑦案件紹介 17:40-18:00 20 ⑧今後学ぶと良いこと *適宜休憩時間を設けます
3. 3 ©BrainPad Inc. Strictly Confidential この講義では、数理最適化の基礎知識を習得していただくことが目標です。 本研修のゴール ビジネス職の ゴール 最適化でできることや最適化PJの進め方を知る  「最適化」、「最適解」というビジネス用語を使う時に目的関数、制約条件は何なのかまでを意識して”いい かんじ”の中身を言語化できるようにする  数理最適化でできることを理解し、クライアント/PJメンバーとのコミュニケーションを円滑に進められるよ うにする 技術職の ゴール 簡単な最適化問題であれば自力で定式化・実装できる  最適化問題の定式化のコツと実装の流れを問題演習を通して理解する  現実問題に対しても定式化をして最適化問題に落とし込むことができるようになる
4. ©BrainPad Inc. Strictly Confidential ①数理最適化イントロダクション
5. ©BrainPad Inc. Strictly Confidential 5 1. 最適化問題・数理最適化とは 2. なぜ最適化を学ぶのか 3. ブレインパッドにおける最適化案件 4. 最適化案件の進め方 数理最適化イントロダクション
6. 6 ©BrainPad Inc. Strictly Confidential 最適化問題: 与えられた制約条件のもとで目的関数の値を最大(最小)にする解を求める問題 数理最適化: 最適化問題を解くことを通じて現実における意思決定や問題解決を実現する技術 最適化問題・数理最適化とは 最適化問題1 最適化問題2 配送計画問題 機械学習における”学習” 目的関数: • 配送トラックの最小化 • 移動距離最小化、. . . 制約条件: • 全ての店舗を訪問 • トラックの積載量の上限、. . . 目的関数: 損失関数の最小化 制約条件: 𝜃に対する制約 小売A 小売B 小売C 倉庫 機械学習モデル パラメータ𝜃 入力データ 𝑥 正解データ 𝑦 予測データ ො 𝑦 学習データ(𝑥, 𝑦) 損失関数 (異なり具合を評価)
7. 7 ©BrainPad Inc. Strictly Confidential 実は今日のチーム分けも最適化問題で行っています！ 今日の講義が終わる頃には下の式の意味がわかるようになっているはずです 最適化問題・数理最適化とは 集合 受講生の集合 グループの集合 問題 定数 ：受講生 i の最適化のスキル ：受講生 i のPythonのスキル ：全員のスキルの総和をグルー プ数で割った値
8. 8 ©BrainPad Inc. Strictly Confidential 機械学習と数理最適化はどう違うのかと思われた方もいるかと思います 機械学習は予測を行うのに対して、数理最適化は実際に何をするのかの意思決定を行うという違いがあります 例として天気予報をもとに傘を持っていくか決める状況を考えます 最適化問題・数理最適化とは 機械学習（予測） 数理最適化（意思決定） *余談ですが講師は折り畳み傘を常に持ち歩くが最適解だと考えています *前述の機械学習における”学習”のように様々な分野の基盤技術としての側面もあります • 気温 • 湿度 • 気象衛生 • etc. . . 降水確率90% 説明変数 予測モデル 目的変数 雨が降りそうなの で傘を持っていく 機械学習においては説明変数を入力として 予測モデルを用いて目的変数を予測します 数理モデル(最適化問題) 求解 目的関数 • 雨に濡れた時の”嫌さ”と傘を 持っていく時の”煩わしさ”の 総和を最小化 制約条件 • 手荷物の多さ(両手が塞がっ ていないか？) • etc . . . 最適化問題を解いた結 果傘を持っていくのが 最適化である 数理最適化では予測モデルの結果をもとに 数理モデルを用いて意思決定します この意思決定を数理モデルに 基づいて解決！
9. 9 ©BrainPad Inc. Strictly Confidential 実案件においてもデータ分析を通してデータドリブンな意思決定を行いたいという場面はたくさんあります 意思決定を行う状況において最適化の活躍の余地があります。以下に広告予算配分を例に説明します なぜ最適化を学ぶのか 予測(機械学習) 意思決定(数理最適化) 可視化 まずは実績データの可視化を通 して現状の確認を行います 例) • 広告費用と利益の散布図 • 広告費用とCVの散布図 • 広告費用の時系列 次にどのくらいの広告費用をか けるとどのくらいの利益やCVが 得られるかの予測モデルを構築 します 最後に予測モデルをもとに予算 上限を超えない下で利益やCVを 最大化する最適化問題を解きま す 得られた最適な予算配分 可視化・予測は「現状どうか？」や「今後どうなる？」には答えてくれるが 「どうしたら良い？」には明示的に答えてくれない *そうは言ってもROIやデータが得られないなどの観点から最適化まで行わずに 可視化や予測で十分という状況も往々にしてあります 広告費用 CV数 広告A 広告B 広告費用 CV数 広告A 広告B 2025/04 広告費用(万円) 2025/05 2025/06
10. 10 ©BrainPad Inc. Strictly Confidential 最適化案件は以下の一連の手続きからなります 定式化がアルゴリズムが一発で決まることは稀でお客さんのフィードバックをもらいながら何回もサイクルを回します 最適化案件の進め方 現 実 問 題 最 適 化 問 題 計 算 結 果 問 題 解 決 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討 https://zenn.dev/umepon/articles/50a74c75f32096875d94 を参考に作成
11. 11 ©BrainPad Inc. Strictly Confidential 本日の研修では典型問題を通して定式化→ソルバーによる求解の流れを学んでいただき、 最後に実践演習として一連のサイクルを手を動かしながら学んでもらいます 最適化案件の進め方 https://zenn.dev/umepon/articles/50a74c75f32096875d94 を参考に作成 実践演習 線形計画 定式化&実装 整数計画 定式化&実装 混合整数計画 定式化&実装
12. 12 ©BrainPad Inc. Strictly Confidential 最適化案件の進め方 | 定式化 現 実 問 題 最 適 化 問 題 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討 まず初めに現実問題を数式を使って最適化問題として記述する必要があります 目的関数： 最大化・最小化 したい指標 決定変数： 最適化により決 定したい値 制約式： 指標の最適化に あたっての制約 生産スケジュールの作成を自動 化したい。 製品の数は〇〇で各商品に対し て△△の条件を満たす必要があ り…、××のあとは□時間イン ターバルを空ける必要があり… 定式化 ※定式化イメージ
13. 13 ©BrainPad Inc. Strictly Confidential 最適化案件の進め方 | 最適化問題を解く 現 実 問 題 現実問題を最適化問題として記述できれば、その問題をどう解くかに専念することができます 最適化問題を解くアプローチとしては大きく以下の２通りに大別されます (1)汎用ソルバーによる解法 幅広い問題に対して適用可能なアルゴリズムを予め実装 したソフトウェアを利用する方法 制約条件の変更が生じても比較的変更が容易 (2)フルスクラッチアルゴリズムによる解法 自分で1から求解アルゴリズムを実装する方法 問題固有の性質を使うことができるので求解性能は高い 一方で保守性が低くなりやすい 求 解 性 能 汎用性 (1)汎用解法 (2)フルスクラッチ それぞれのアプローチには 性能・汎用性についてのトレード オフが存在する 案件ではソルバーが使われること が多い 最 適 化 問 題 計 算 結 果 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討
14. 14 ©BrainPad Inc. Strictly Confidential 最適化案件の進め方 | 解の確認 ・ 定式化の修正 考えた定式化が一発でうまくいくことはまずあり得ません 最適化問題の定式化やアルゴリズムを見直しながら改善を繰り返します ソルバーやアルゴリズムによって解を得た後は結果を可 視化を行います 生産計画における生産順番を表すガントチャート可視化の例 工場の設備上、製品Aの次に製品B を生産することはできません 定式化の修正 ⋮ 部分的な修正で良いこともあればモデルの 大部分を変更しなければならない破滅的変更を 伴う場合もあります 現 実 問 題 最 適 化 問 題 計 算 結 果 問 題 解 決 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討 2024/12/1 12:00 2024/12/4 12:00 2024/12/2 12:00 2024/12/3 12:00 休 み 製品A 製品B 製品E 製品C 製品D 休 み
15. ©BrainPad Inc. Strictly Confidential ②線形計画 定式化
16. ©BrainPad Inc. Strictly Confidential 16 1. 最適化問題の基礎知識 2. 線形計画問題とは 3. 例題 4. 類題演習 5. 質疑応答 線形計画定式化
17. 17 ©BrainPad Inc. Strictly Confidential ひとくちに最適化問題と言ってもさまざまな最適化問題が存在します 決定変数、目的関数、制約条件の性質によって以下のように分類されることがあります 最適化問題の基礎知識 | 代表的な最適化問題 引用元：梅谷俊治「しっかり学ぶ数理最適化」 連続最適化 決定変数が実数値のような連続的な値を取る最適化問題 離散最適化（組合せ最適化） 決定変数が整数値や{0, 1}の2値のような離散的な値をとる最適 化問題や、最適解を含む解の集合が順列やネットワークなど組 合せ的な構造を持つ最適化問題 非線形計画問題(NLP) 2次計画問題(QP) 線形計画問題(LP) 整数計画問題(IP) 混合整数計画問題(MIP) ネットワーク最適化問題
18. 18 ©BrainPad Inc. Strictly Confidential 本講義では線形計画問題、整数計画問題、混合整数計画問題について解説します 最適化問題の基礎知識 | 代表的な最適化問題 引用元：梅谷俊治「しっかり学ぶ数理最適化」 線形計画問題(LP) 整数計画問題(IP) 混合整数計画問題(MIP)
19. 19 ©BrainPad Inc. Strictly Confidential 最適化問題は以上のような目的関数と制約条件から構成されます 𝑓(𝑥) 𝑥 最 小 化 局所最適解 最適解 実行可能領域 続いて基本的な最適化における用語について確認していきます 最適化問題の基礎知識 | 用語 最適値 引用元：梅谷俊治「しっかり学ぶ数理最適化」 𝑆 用語 意味 決定変数 最適化対象の変数 (上の問題の𝑥) 解 決定変数に割り当てられた値 実行可能解 制約条件を満たす解 実行可能領域 実行可能解全体の集合 (大域)最適解 目的関数の値が最大or最小となる解 局所最適解 近傍内の任意の解よりも目的関数値が大きいor小さい解 最適値 最適解における目的関数の値
20. 20 ©BrainPad Inc. Strictly Confidential 最適化問題は必ず最適解が存在するとは限りません そもそも実行可能解が存在しなかったり、いくらでも目的関数を改善できてしまう状況が存在します 最適化問題の基礎知識 | 用語 𝑓(𝑥) 𝑥 最 小 化 最適解 実行可能領域 𝑓(𝑥) 𝑥 最 大 化 実行可能領域 𝑥を大きくすることでいくら でも目的関数値 𝑓(𝑥) の値を 大きくできてしまう 最適解が存在 実行不能 非有界 𝑓(𝑥) 𝑥 最 小 化 実行可能領域が空集合 制約条件 𝑥 ≤ 1 かつ 3 ≤ 𝑥 引用元：梅谷俊治「しっかり学ぶ数理最適化」
21. 21 ©BrainPad Inc. Strictly Confidential 線形計画問題とは「いくつかの一次不等式や等式を制約として、ある一次関数を最大化・最小化する問題」のことです 例えば以下のような問題があります 線形計画問題(LP: Linear Programming)とは 例1 例2
22. 22 ©BrainPad Inc. Strictly Confidential 何やら難しく聞こえるかもしれませんが、実は線形計画問題は高校数学でも登場しています 線形計画問題(LP: Linear Programming)とは 引用元：高校数学の美しい物語
23. 23 ©BrainPad Inc. Strictly Confidential 線形計画問題の基本的な性質 線形計画問題(LP: Linear Programming)とは ①最大化と最小化は等価 (−1) × (−1) = 1のようなイメージです 最尤推定において”尤度の最大化”を行う代わりに”負の対数尤度の最小化”を行うのもこの 性質に基づいています* もちろん実務においては目的関数によって最大化or最小化が自然という場合はあります 等価 等価 *単調増加関数の性質も使っています *慣習的に連続最適化においては最小化問題として扱うことが多いです
24. 24 ©BrainPad Inc. Strictly Confidential 線形計画問題の基本的な性質 線形計画問題(LP: Linear Programming)とは ②不等式制約と等式制約は等価 変形可能 等式は不等式に書き換えられ、不等式も等式に書き換えることができるので 全体として不等式制約と等式制約は等価となります 変形可能
25. 25 ©BrainPad Inc. Strictly Confidential 簡易的なビジネス課題を最適化問題として定式化に取り組みます 例題 ＆ 類題演習 | 最適化問題の定式化 例題 & 類題演習 現 実 問 題 最 適 化 問 題 定式化
26. 26 ©BrainPad Inc. Strictly Confidential 定式化を行う際は以下の順番を意識すると見通しが良くなります 例題 | 最適化問題を定式化する流れ 1. 決定変数を決める 2. 目的関数を決定変数を用いて表現する 3. 制約条件を決定変数を用いて表現する 目的関数： 最大化・最小化 したい指標 決定変数： 最適化により決 定したい値 制約式： 指標の最適化に あたっての制約 最終的に作りたい定式化
27. 27 ©BrainPad Inc. Strictly Confidential 実際に簡易的なビジネス課題を最適化問題として定式化してみましょう 例題 | 飲料の生産量最適化 ￥3,000 ￥2,000 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあ たり2,000円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーを 何kgずつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫の通り 問題文 フルーツ ジュース フルーツ ティー 材料在庫量 リンゴ 2 5 500 オレンジ 4 2 300 材料 商品 2kg 4kg 5kg 2kg
28. 28 ©BrainPad Inc. Strictly Confidential まず決定変数を定義します 例題 | 解説(1/3) 決定変数を決めよう 問題文 考え方 • 本問で決めたいことは「フルーツジュースとフルーツティー を何kgずつ作るか」 • 従ってひとまず決定変数は以下のようにおいてみる • フルーツジュースを作る量 𝑥1 kg • フルーツティーを作る量 𝑥2 kg ￥3,000 ￥2,000 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあ たり2,000円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーを 何kgずつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫の通り フルーツ ジュース フルーツ ティー 材料在庫量 リンゴ 2 5 500 オレンジ 4 2 300 材料 商品 2kg 4kg 5kg 2kg
29. 29 ©BrainPad Inc. Strictly Confidential 次に目的関数を決定変数を用いて表します 例題 | 解説(2/3) 目的関数を決めよう 問題文 考え方 • 本問では「売上を最大化したい」 • 売上はジュースの売上とティーの売上の合計 • 式で書くと、 • 売上 = ジュースの売上+ ティーの売上 = 3000 × 𝑥1 + 2000 × 𝑥2 • ジュースを作る量 𝑥1 kg • ティーを作る量 𝑥2 kg あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあ たり2,000円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーを 何kgずつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫の通り フルーツ ジュース フルーツ ティー 材料在庫量 リンゴ 2 5 500 オレンジ 4 2 300 材料 商品
30. 30 ©BrainPad Inc. Strictly Confidential フルーツ ジュース フルーツ ティー 材料在庫量 リンゴ 2 5 500 オレンジ 4 2 300 材料 商品 最後に制約条件を決定変数を用いて表します 例題 | 解説(3/3) 制約条件を決めよう 考え方 • 本問での制約条件は材料の在庫数 • 材料としてはリンゴ、オレンジの二つがあるのでそれぞれに ついて在庫量の制約を考えれば良い • リンゴの材料の制約は、 ジュースで使うリンゴ＋ティーで使うリンゴ≦リンゴの在庫 ⇔ 1kgのジュースに使うリンゴの量 × ジュース生産量 + 1kgのティーに使うリンゴの量 × ティー生産量 ≦リンゴ の在庫 • 式で書くと • 同様にオレンジの材料の制約は 問題文 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあ たり2,000円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーを 何kgずつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫の通り
31. 31 ©BrainPad Inc. Strictly Confidential 得られた決定変数、目的関数、制約式を一つにすると下記の通りとなります 例題 | 解答 例題の定式化
32. 32 ©BrainPad Inc. Strictly Confidential 下記の問題を演習として定式化してみましょう 類題演習 | 飲料の生産量最適化 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあたり2,000円、 リンゴジュースは1kgあたり500円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーとリンゴジュース をいくつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫数の通り • リンゴジュースはフルーツジュース以上の量を作ることとする 問題文 • この制約が必要になるのはどんなとき でしょうか？ • ⇒ 例えば、リンゴジュースは、 • フルーツジュースとセット販売 • 単品で販売 の2通りで売る時など フルーツ ジュース フルーツ ティー リンゴ ジュース 材料在庫量 リンゴ 2 5 1 500 オレンジ 4 2 0 300 材料 商品
33. 33 ©BrainPad Inc. Strictly Confidential 例題を参考にしながら、類題の定式化を手元のノートに書いてください。 グループで相談してOKです。質問や疑問点があれば近くのTAまで聞いてください！ 類題演習 | 飲料の生産量最適化 作業時間（10分）
34. 34 ©BrainPad Inc. Strictly Confidential 類題演習 | 解説(1/3) 決定変数を決めよう 考え方 • 基本的な考え方は先ほどと同様です • 本問で決めたいことは「フルーツジュース、フルーツティー、 リンゴジュースをどのくらいの量作るか」 • 決定変数をとりあえず以下のようにおいてみる • フルーツジュースを作る量 𝑥1 kg • フルーツティーを作る量 𝑥2 kg • リンゴジュースを作る量 𝑥3 kg まず決定変数を決めます 問題文 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあたり 2,000円、リンゴジュースは1kgあたり500円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーとリン ゴジュースをいくつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫数の通り • リンゴジュースはフルーツジュース以上の量を作ることとする フルーツ ジュース フルーツ ティー リンゴ ジュース 材料在庫量 リンゴ 2 5 1 500 オレンジ 4 2 0 300 材料 商品
35. 35 ©BrainPad Inc. Strictly Confidential 類題演習 | 解説(2/3) 目的関数を決めよう 問題文 考え方 • 本問では「売上を最大化したい」 • 売上は、フルーツジュースとフルーツティーとリンゴジュー スの売上の合計 • フルーツジュースの売上 = 1kgあたりのフルーツ ジュースの売値 × フルーツジュースの生産量 • フルーツティーの売上 = 1kgあたりのフルーツティー の売値 × フルーツティーの生産量 • リンゴジュースの売上 = 1kgあたりのリンゴジュース の売値 × リンゴジュースの生産量 • 式で書くと 次に決定変数を用いて目的関数を表します あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあたり 2,000円、リンゴジュースは1kgあたり500円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーとリン ゴジュースをいくつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫数の通り • リンゴジュースはフルーツジュース以上の量を作ることとする フルーツ ジュース フルーツ ティー リンゴ ジュース 材料在庫量 リンゴ 2 5 1 500 オレンジ 4 2 0 300 材料 商品
36. 36 ©BrainPad Inc. Strictly Confidential 類題演習 | 解説(3/3) 制約条件を決めよう 考え方 • 本問での制約条件は2種類の制約を考える必要がある • 材料 (リンゴ、オレンジ)の在庫量制約 • リンゴジュースはフルーツジュースよりも多く作る • 在庫数制約は例題と同様に考えることができる • リンゴの在庫制約 • オレンジの在庫制約 • リンゴジュースはフルーツジュースよりも多く作る 最後に決定変数を用いて制約条件を表します 問題文 あなたは飲料を製造・販売している業者です。 フルーツジュースは1kgあたり3,000円、フルーツティーは1kgあたり 2,000円、リンゴジュースは1kgあたり500円で販売しています。 売上を最大化するには、フルーツジュースとフルーツティーとリン ゴジュースをいくつ作ればよいでしょうか？ ただし、製造に関して、下記の条件がある • 各商品は、リンゴとオレンジを材料とする • 各商品を1kg作るのに必要な材料の量は、下表の通り • 使える材料の量は、下表の在庫数の通り • リンゴジュースはフルーツジュース以上の量を作ることとする フルーツ ジュース フルーツ ティー リンゴ ジュース 材料在庫量 リンゴ 2 5 1 500 オレンジ 4 2 0 300 材料 商品
37. 37 ©BrainPad Inc. Strictly Confidential 得られた決定変数、目的関数、制約式を一つにすると下記の通りとなります 類題演習 | 解答 類題の定式化
38. ©BrainPad Inc. Strictly Confidential ③線形計画 実装
39. ©BrainPad Inc. Strictly Confidential 39 1. 最適化問題の解き方 2. 例題 3. 類題演習 4. 質疑応答 線形計画実装
40. 40 ©BrainPad Inc. Strictly Confidential 先程までで最適化問題に定式化する方法を学びました。これ以降はどうやって解くかについて説明します 本講義では特に汎用ソルバーを用いて最適化問題を解く方法について学びます 最適化問題の解き方 モデラー ソルバー 再掲 定式化した問題をソルバーが解釈可能な形にするための変換器 線形計画問題ではLPファイルを通してソルバーに問題を渡します* MAXIMIZE 2*x_0 + 4*x_1 + 1*x_2 + 3*x_3 + 0 SUBJECT TO _C1: 3 x_0 + 5 x_1 + x_2 + 4 x_3 <= 8 VARIABLES 0 <= x_0 <= 1 Integer 0 <= x_1 <= 1 Integer 0 <= x_2 <= 1 Integer 0 <= x_3 <= 1 Integer model.py model.lp 予めアルゴリズムが実装されたパッケージ 線形計画問題では • Gurobi (有償) • SCIP (無償) • Cbc (無償) などのソルバーが存在します SCIP Cbc (1)汎用ソルバーによる解法 幅広い問題に対して適用可能なアルゴリズムを予め実装 したソフトウェアを利用する方法 制約条件の変更が生じても比較的変更が容易 (2)フルスクラッチアルゴリズムによる解法 自分で1から求解アルゴリズムを実装する方法 問題固有の性質を使うことができるので求解性能は高い 一方で保守性が低くなりやすい 求 解 性 能 汎用性 (1)汎用解法 (2)フルスクラッチ それぞれのアプローチには 性能・汎用性についてのトレード オフが存在する 案件ではソルバーが使われること が多い モデラー
41. 41 ©BrainPad Inc. Strictly Confidential Pythonでよく使われるモデラーやソルバーとしては以下のようなものがあります モデル作成の流れはどのモデラーでも共通する部分が多いです 最適化問題の解き方 モデラー ソルバー PuLP CP-SAT pywraplp SCIP CPLEX Cbc CP-SAT *使用可能なソルバー、モデラーの組合せが存在する 1. 問題の定義 model = Model(name=‘sample’) 2. 決定変数の実装 x[i] = IntVar(name=f‘x{i}’, LB=0, UB=10) 3. 目的関数の実装 model += 2*x[0]+3*x[1]+x[3] 4. 制約条件の実装 model += 3*x[0]+6*x[1]+2*x[2]<=21 5. 求解 model.optimize() 6. 求めた解の値の取得 x[i].value() モデル作成の流れ 機械学習におけるmodel.fit() → model.predict()のよう に最適化モデラーにおいてもモデリングの流れが存在します モデラーに応じて細かい書き方は異なりますが、使い方の流れ の大枠は共通しています gurobipy 引用：https://www.coin-or.org/、 https://www.gurobi.com/、https://github.com/scipopt、 https://crescointl.com/product/third-party-products/ibm-products/ibm-ilog-cplex-optimization-studio/、https://developers.google.com/optimization/routing/routing_options?hl=ja PySCIPOpt
42. 42 ©BrainPad Inc. Strictly Confidential 簡易的なビジネス課題を想定し、ソルバーによる求解に取り組みます 例題 ＆ 類題演習 | ソルバーによる求解 例題 & 類題演習 現 実 問 題 最 適 化 問 題 計 算 結 果 定式化 （アルゴリズム or） ソルバー による求解
43. 43 ©BrainPad Inc. Strictly Confidential 先程までの例題を実際にソルバーに解かせてみましょう 今回はPuLPというモデラーとCbcというソルバーを用いて最適化問題を解きます 例題（実装） 例題の定式化
44. 44 ©BrainPad Inc. Strictly Confidential 最初に、どんな問題（最大化/最小化）を解きたいのかを定義します 例題 | 解説（1/5）問題の定義をしよう 問題文 考え方 • LpProblemで問題を定義する。 • name：最適化問題の名前 • sense：目的関数を最大化 or 最小化するか import pulp model = pulp.LpProblem(name= ='例題', sense=pulp.LpMaximize)
45. 45 ©BrainPad Inc. Strictly Confidential 次に決定変数を実装します 例題 | 解説（2/5）決定変数を実装しよう 問題文 考え方 x1 = pulp.LpVariable(name='x1', lowBound=0, upBound=None, cat='Continuous') x2 = pulp.LpVariable(name='x2', lowBound=0, upBound=None, cat='Continuous') • LpVariableで決定変数を定義します。 ◦ name：変数の名前を表す ◦ lowBound：変数の取る値の最小値 ◦ upBound：変数の取る値の最大値 ◦ cat：変数の型 ▪ continuousは実数
46. 46 ©BrainPad Inc. Strictly Confidential 次に目的関数を実装します 例題 | 解説（3/5）目的関数を実装しよう 問題文 考え方 • 目的関数を以下のように実装します • 間違えている例 • 多くのモデラーは複合代入演算子で目的関数、制約 式の定義を行うので最初は違和感を感じるかもしれ ません model += 3000 * x1 + 2000 * x2 model = 3000 * x1 + 2000 * x2
47. 47 ©BrainPad Inc. Strictly Confidential 次に制約条件を実装します 例題 | 解説（4/5）制約条件を実装しよう 問題文 考え方 • 制約条件を以下のように実装します model += 2 * x1 + 5 * x2 <= 500 model += 4 * x1 + 2 * x2 <= 300
48. 48 ©BrainPad Inc. Strictly Confidential 最適化問題の実装が完了したので実際にソルバーに解かせてみます 例題 | 解説（5/5）解を求めてみよう model.solve() print('Status:', pulp.LpStatus[model.status]) print('x1=', x1.value(), 'x2=', x2.value()) Solveメソッドを呼んで最適化問題を解きます Status: Optimal x1= 31.25 x2=87.5 print文の結果は となって最適解を得られました 変数.value() は忘れやすいので注意
49. 49 ©BrainPad Inc. Strictly Confidential 同様の問題を10分で自分で実装してみましょう 類題演習 類題の定式化
50. 50 ©BrainPad Inc. Strictly Confidential 類題演習 作業時間（10分） 分からない所などあったら、遠慮なく声をかけてください。 5分経過したらヒントを出します。
51. ©BrainPad Inc. Strictly Confidential ④整数計画問題 定式化&実装
52. ©BrainPad Inc. Strictly Confidential 52 1. 整数計画問題とは 2. 例題 3. 類題演習 4. 質疑応答 整数計画問題 定式化&実装
53. 53 ©BrainPad Inc. Strictly Confidential 決定変数が全て整数であるような最適化問題を整数計画問題と呼びます 目的関数や決定変数の取り得る値によって問題が分類されます 整数計画問題(IP: Integer Programming)とは  0-1整数計画問題 (0-1 integer programming) 全ての変数が0か1かという制約が課される問題です。ある選択肢を「選択する・選択しない」、あるルートを「通る・ 通らない」といったon/offで表せるものはこの問題になります。  線形整数計画問題 決定変数が全て整数で、目的関数と制約条件が線形で表される問題です。  非線形整数計画問題 目的関数もしくは制約条件に線形ではないものを含んだより広い問題です。 目的関数をとして二乗誤差などを設定した場合はこの問題となります。 この問題は本講義で解説しているPuLP+Cbcではモデリング・求解できないので他のモデラー・ソルバーを使う必要が あります
54. 54 ©BrainPad Inc. Strictly Confidential 下記のビジネス問題を定式化してみます ポイントは①決定変数、②目的関数、③制約式の順に作ることです 例題 | ナップサック問題 問題文 あなたは、商品をナップサック（カバン）に詰めて販売している行商です。 ナップサックに、どの商品を詰めたら、総収入を最大化できるでしょうか？ ただし、商品とナップサックには、次の条件があります。 • 商品は、４種類あり、それぞれ重さと価値が違う（下表参照）。 • ナップサックには、合計で８ｋｇまでしか詰められない。 商品 1 2 3 4 価値（万円） 2 4 1 3 重さ（kg） 3 5 1 4 最もお金を稼ぐには どう詰めるか？
55. 55 ©BrainPad Inc. Strictly Confidential 最初に、最適化で決定する量となる決定変数を決めます 例題 | 定式化 解説（1/3）決定変数を決めよう あなたは、商品をナップサック（カバン）に詰めて販売してい る行商です。ナップサックに、どの商品を詰めたら、総収入を 最大化できるでしょうか？ ただし、商品とナップサックには、次の条件がある。 • 商品は、４種類あり、それぞれ重さと価値が違う（下表）。 • ナップサックには、合計で８ｋｇまでしか詰められない。 問題文 考え方 • 本問で決めたいことは、どの商品をナップサックに詰めるか • 決定変数は 商品 1 2 3 4 価値（万円） 2 4 1 3 重さ（kg） 3 5 1 4 商品iをナップサックに詰める 商品iをナップサックに詰めない
56. 56 ©BrainPad Inc. Strictly Confidential 次に、最大化（or 最小化）をしたい事象を目的関数として定義します 例題 | 定式化 解説（2/3）目的関数を決めよう あなたは、商品をナップサック（カバン）に詰めて販売してい る行商です。ナップサックに、どの商品を詰めたら、総収入を 最大化できるでしょうか？ ただし、商品とナップサックには、次の条件がある。 • 商品は、４種類あり、それぞれ重さと価値が違う（下表）。 • ナップサックには、合計で８ｋｇまでしか詰められない。 問題文 考え方 • 本問で決めたいことは、どの商品を詰めると、総収入が 最大化できるか • （再掲）決定変数は • 目的関数を決定変数を使って表現すると 商品 1 2 3 4 価値（万円） 2 4 1 3 重さ（kg） 3 5 1 4 商品iをナップサックに詰める 商品iをナップサックに詰めない
57. 57 ©BrainPad Inc. Strictly Confidential 最後に、決定変数や目的関数が満たすべき制約を表した制約条件を決めます 例題 | 定式化 解説（3/3）制約条件を決めよう あなたは、商品をナップサック（カバン）に詰めて販売してい る行商です。ナップサックに、どの商品を詰めたら、総収入を 最大化できるでしょうか？ ただし、商品とナップサックには、次の条件がある。 • 商品は、４種類あり、それぞれ重さと価値が違う（下表）。 • ナップサックには、合計で８ｋｇまでしか詰められない。 問題文 考え方 • ナップサックに8kgまでしか詰められないが制約条件です。 • （再掲）決定変数は • 決定変数を用いると、制約条件は 商品 1 2 3 4 価値（万円） 2 4 1 3 重さ（kg） 3 5 1 4 商品iをナップサックに詰める 商品iをナップサックに詰めない
58. 58 ©BrainPad Inc. Strictly Confidential 得られた決定変数、目的関数、制約式を1つにすると下記の通りになります 例題 | ナップサック問題 解説 例題の定式化
59. 59 ©BrainPad Inc. Strictly Confidential 今までは価値や重さ、容量の値をベタ打ちしていましたが、実際は色々な入力データが入ってきます そのような状況に対応できるように集合と総和記号を使って定式化を一般化しましょう 例題 | ナップサック問題 解説 例題の定式化 例題の定式化 (一般化) :商品の集合 :商品𝑖の価値 :商品𝑖の重さ :ナップサックの容量 集合と定数の定義 集合と総和記号(∑)の使い方については 次ページ参照
60. 60 ©BrainPad Inc. Strictly Confidential さらに複数の制約式をまとめる 制約式に現れる足し算をまとめる 最適化問題の定式化では集合や総和記号( ∑ )がよく出てきます 補足 集合と総和記号 ※行列を使って制約をまとめることもあります (例: 𝐴𝑥 ≤ 𝑏, 𝐴 ∈ ℝ𝑚×𝑛, 𝑥 ∈ ℝ𝑛, 𝑏 ∈ ℝ𝑚)
61. 61 ©BrainPad Inc. Strictly Confidential ここまでの話を踏まえて定式化を行う時は以下の順番を意識すると見通しが良くなります 基本的な流れは先程と同じですが、まず集合を定義してから決定変数を決めるようにしましょう 最適化問題を定式化する流れ 1. 集合,定数を定義する 2. 決定変数を決める 3. 目的関数を決定変数を用いて表現する 4. 制約条件を決定変数を用いて表現する :商品の集合 :商品𝑖の価値 :商品𝑖の重さ :ナップサックの容量 :商品𝑖を選択するか否か
62. 62 ©BrainPad Inc. Strictly Confidential 先ほどのナップサック問題をPythonとpulpを用いて、実装しましょう コードを書く際も汎用的なコーディングを行うために一般化した定式化を意識しましょう 例題 | 実装 ナップサック問題 例題の定式化 例題の定式化 (一般化) :商品の集合 :商品𝑖の価値 :商品𝑖の重さ :ナップサックの容量 集合と定数の定義 入力の受け取り 問題のインスタンス化
63. 63 ©BrainPad Inc. Strictly Confidential 最初に、入力データの集合、定数を定義します 実際の案件ではエクセルファイル経由でdataclassを用いたりして入力データを受け取ります 例題 | 実装 解説（1/6）集合、定数の定義をしよう 問題文 考え方 • 今回は入力データの定義を行う • 商品の集合をリスト、価値を辞書で定義する I = [1,2,3,4] v = {1:2, 2:4, 3:1, 4:3} w = {1:3, 2:5, 3:1, 4:4} C = 8
64. 64 ©BrainPad Inc. Strictly Confidential 次に、どんな問題（最大化/最小化）を解きたいのかを定義します 例題 | 実装 解説（2/6）問題の定義をしよう 問題文 考え方 • LpProblemで問題を定義する。 • name：最適化問題の名前 • sense：目的関数を最大化 or 最小化するか import pulp model = pulp.LpProblem(name='knapsack', sense=pulp.LpMaximize)
65. 65 ©BrainPad Inc. Strictly Confidential 次に、決定変数を実装します 例題 | 実装 解説（3/6）決定変数を実装しよう 問題文 考え方 • LpVariableで決定変数を定義する。 • name：変数の名前 • cat：変数の型 • {0, 1}変数は’Binary’と指定する • 商品集合Iを用いた内包表記で1行で定義を行う • pulpでは以下のように書いても同様の辞書に格納された決定 変数を定義することができる x = {i: pulp.Lpvariable(name=f’x{i}’, cat=‘Binary’) for i in I} x = pulp.Lpvariable.dicts(’x’, I, cat=’Binary’)
66. 66 ©BrainPad Inc. Strictly Confidential 次に、目的関数を実装します 例題 | 実装 解説（4/6）目的関数を実装しよう 問題文 考え方 • 目的変数を下記のように実装する • pulp.lpsum(リスト)でリストに格納された変数の総和を表現 できる model += pulp.lpSum(v[i]*x[i] for i in I)
67. 67 ©BrainPad Inc. Strictly Confidential 次に、制約条件を実装します 例題 | 実装 解説（5/6）制約条件を実装しよう 問題文 考え方 • 制約条件を下記の用に実装する。 model += pulp.lpSum(w[i]*x[i] for i in I) <= C
68. 68 ©BrainPad Inc. Strictly Confidential 最後に、モデルを実行することで解が求まります 例題 | 実装 解説（6/6）解を求めてみよう モデル実行の実装 model.solve() print('Status:', pulp.LpStatus[model.status]) print('x1=', x1.value(), 'x2=', x2.value(),'x3=', x3.value(), 'x4=', x4.value()) Print文の結果 Status: Optimal x1= 1.0 x2= 0.0 x3= 1.0 x4= 1.0
69. 69 ©BrainPad Inc. Strictly Confidential 下記の問題を制限時間10分以内に定式化してください（ご自身のノートに書いてください） 類題演習 | ビンパッキング問題 問題文 あなたは、１０個の商品をいくつかの箱に詰めて、発送しようとしています。 どのように商品を組み合わせて箱詰めしたら、箱の使用数を最小化できるでしょうか？ ただし、商品と箱には、次の条件がある。 • 商品は、１０種類（１種類につき１個）あり、それぞれ重さが違う（下表参照）。 • 箱１つには、合計１０ｋｇの商品しか詰められない。 • 箱は、合計１０個ある。 • 商品は、余すことなく箱詰めする。 商品 1 2 3 4 5 6 7 8 9 10 重さ （kg） 3 5 7 4 8 8 6 9 6 5 ちなみに”ビン” はbottleでなく 大箱のこと。
70. 70 ©BrainPad Inc. Strictly Confidential ビンパッキング問題を制限時間10分以内に定式化してください（ご自身で手元のノートに書いて下さい） 類題演習 | ビンパッキング問題 作業時間（10分） 分からない所などあったら、遠慮なく声をかけてください。 5分したらヒントを出します。
71. 71 ©BrainPad Inc. Strictly Confidential 定式化を行う時は以下の順番を意識すると見通しが良くなります 最適化問題を定式化する流れ 1. 集合,定数を定義する 2. 決定変数を決める 3. 目的関数を決定変数を用いて表現する 4. 制約条件を決定変数を用いて表現する :商品の集合 :商品𝑖の価値 :商品𝑖の重さ :ナップサックの容量 :商品𝑖を選択するか否か 再掲
72. 72 ©BrainPad Inc. Strictly Confidential 最初に、最適化で決定する量となる決定変数を決めます 類題演習 | 定式化 解説（1/3）決定変数を決めよう あなたは、１０個の商品をいくつかの箱に詰めて、発送しよう としています。どのように商品を組み合わせ箱詰めしたら、箱 の使用数を最小化できるでしょうか？ ただし、商品と箱には、次の条件がある。 • 商品は、１０種類（１種類につき１個）あり、 それぞれ重さが違う（下表参照）。 • 箱１つには、合計１０ｋｇの商品しか詰められない。 • 箱は、合計１０個ある。 • 商品は、余すことなく箱詰めする。 問題文 考え方 • 本問で決めたいことは、箱にどの商品を詰めるか • 決定変数は、 • 箱iを使うかどうか • 箱iに商品jを詰めるかどうか 商品 1 2 3 4 5 6 7 8 9 10 重さ (KG) 3 5 7 4 8 8 6 9 6 5 箱iに商品を詰める場合 上記以外の場合 箱iに商品jを詰める場合 上記以外の場合
73. 73 ©BrainPad Inc. Strictly Confidential 次に、最大化（or 最小化）をしたい事象を目的関数として定義します 類題演習 | 定式化 解説（2/3）目的関数を決めよう あなたは、１０個の商品をいくつかの箱に詰めて、発送しよう としています。どのように商品を組み合わせ箱詰めしたら、箱 の使用数を最小化できるでしょうか？ ただし、商品と箱には、次の条件がある。 • 商品は、１０種類（１種類につき１個）あり、 それぞれ重さが違う（下表参照）。 • 箱１つには、合計１０ｋｇの商品しか詰められない。 • 箱は、合計１０個ある。 • 商品は、余すことなく箱詰めする。 問題文 考え方 • 目的関数は、使う箱の数の最小化 • （再掲）決定変数は、 • 箱iを使うかどうか • そのため、目的関数は、 商品 1 2 3 4 5 6 7 8 9 10 重さ (KG) 3 5 7 4 8 8 6 9 6 5 箱iに商品を詰める場合 上記以外の場合
74. 74 ©BrainPad Inc. Strictly Confidential 最後に、決定変数や目的関数が満たすべき制約を表した制約条件を決めます 類題演習 | 定式化 解説（3/3）制約条件を決めよう あなたは、１０個の商品をいくつかの箱に詰めて、発送しよう としています。どのように商品を組み合わせ箱詰めしたら、箱 の使用数を最小化できるでしょうか？ ただし、商品と箱には、次の条件がある。 • 商品は、１０種類（１種類につき１個）あり、 それぞれ重さが違う（下表参照）。 • 箱１つには、合計１０ｋｇの商品しか詰められない。 • 箱は、合計１０個ある。 • 商品は、余すことなく箱詰めする。 問題文 考え方 • 満たすべき制約は2つある。 • 1つの箱には10Kgしか詰められない i番目の箱に注目すると • 全ての商品を箱詰めする必要がある j番目の商品に着目すると 商品 1 2 3 4 5 6 7 8 9 10 重さ (KG) 3 5 7 4 8 8 6 9 6 5 箱iに入れる商品の重さの合計 箱iに入る重さ y_i = 1→10 y_i = 0 →0
75. 75 ©BrainPad Inc. Strictly Confidential 得られた決定変数、目的関数、制約式を1つにすると下記の通りになります 類題演習 |ビンパッキング問題 解説 類題の定式化
76. 76 ©BrainPad Inc. Strictly Confidential ビンパッキング問題を実際に実装してみましょう 類題演習 | 実装 類題の定式化
77. 77 ©BrainPad Inc. Strictly Confidential ビンパッキング問題を実際に実装してみましょう 作業時間（10分） 分からない所などあったら、遠慮なく声をかけてください。 5分経過したらヒントを出します。 類題演習 | 実装
78. ©BrainPad Inc. Strictly Confidential ⑤混合整数計画問題 定式化&実装
79. ©BrainPad Inc. Strictly Confidential 79 1. 混合整数計画問題とは 2. 例題 3. 演習 4. 質疑応答 整数計画問題 定式化&実装
80. 80 ©BrainPad Inc. Strictly Confidential 実数をとる決定変数と整数をとる決定変数が両方含まれるような問題のことを混合整数計画問題(MIP)と呼びます 混合整数計画問題も目的関数によってさらに分類できます 混合整数計画問題(MIP: Mixed Integer Programming)とは  混合整数線形計画問題問題 (MILP: Mixed Integer Linear Programming) 目的関数が線形な場合の混合整数計画問題です 古くから研究が行われており、さまざまな汎用ソルバーが開発されています (Cbcソルバーもそのひとつ)  混合整数非線形計画問題問題 (MINLP: Mixed Integer NonLinear Programming) 目的関数が非線形な場合の混合整数計画問題で、かなり解きづらい問題です 一方で現実問題を愚直に定式化するとしばしばMINLPが現れます その場合は最適解を出すことを諦めてヒューリスティックアルゴリズムで解くか、頑張って混合線形計画に定式化して MILPソルバーで解くなどの選択肢があります
81. 81 ©BrainPad Inc. Strictly Confidential 例題 | 施設配置問題 問題文 あなたはメーカーの物流担当者で、倉庫から製品を店舗に配送しようとしています 契約可能な倉庫は5つあり、契約すると倉庫費用がかかります どの倉庫を契約し、どれだけ配送すると、倉庫費用と輸送費用を最小化できるでしょうか？ ただし、倉庫と店舗に次の条件がある 1. 倉庫から配送する製品は倉庫容量以下となる 2. 店舗の需要を満たすように配送する 3. 配送費用は、倉庫と店舗間で製品を1単位運ぶのに発生するコストとする 倉庫契約費用: 倉庫容量: 店舗需要
82. 82 ©BrainPad Inc. Strictly Confidential 例題 | 施設配置問題 データ - 店舗 倉庫 S1 S2 S3 S4 F1 10 6 7 4 F2 5 10 3 5 F3 4 2 8 7 F4 5 7 5 5 F5 2 1 1 3 倉庫 倉庫費用 倉庫容量 F1 1000 500 F2 1000 500 F3 1000 400 F4 1000 500 F5 1000 200 店舗 年間需要 量 S1 200 S2 100 S3 200 S4 100 店舗別需要量 倉庫別の費用と容量 倉庫店舗間の輸送費用 : 倉庫𝑖から店舗𝑗への輸送コスト
83. 83 ©BrainPad Inc. Strictly Confidential 最初に、最適化で決定する量となる決定変数を決めます 例題 | 定式化 解説（1/3）決定変数を決めよう あなたはメーカーの物流担当者で、 倉庫から製品を店舗に配送しようとしています。 契約可能な倉庫は5つあり、契約すると倉庫費用がかかります。 どの倉庫を契約し、どれだけ配送すると、 倉庫費用と輸送費用を最小化できるでしょうか？ ただし、倉庫と店舗に次の条件がある。 1. 倉庫から配送する製品は倉庫容量以下となる。 2. 店舗の需要を満たすように配送する。 3. 配送費用は工場と店舗間で製品を1単位運ぶと発生する。 問題文 考え方 • 本問で決めたいことは以下の２つ • どの倉庫と契約するか • どの倉庫からどの店舗へ配送するか • 決定変数は 各倉庫𝑖に対して 倉庫iを契約する 倉庫iを契約しない 倉庫iから店舗jに運ぶ製品の量を
84. 84 ©BrainPad Inc. Strictly Confidential 次に、最大化（or 最小化）をしたい事象を目的関数として定義します 例題 | 定式化 解説（2/3）目的関数を決めよう あなたはメーカーの物流担当者で、 倉庫から製品を店舗に配送しようとしています。 契約可能な倉庫は5つあり、契約すると倉庫費用がかかります。 どの倉庫を契約し、どれだけ配送すると、 倉庫費用と輸送費用を最小化できるでしょうか？ ただし、倉庫と店舗に次の条件がある。 1. 倉庫から配送する製品は倉庫容量以下となる。 2. 店舗の需要を満たすように配送する。 3. 配送費用は工場と店舗間で製品を1単位運ぶと発生する。 問題文 考え方 • 今回の問題は、倉庫費用と輸送費用の合計の最小化 • 倉庫費用は、 • 配送費用は、 :倉庫の集合 :倉庫iの倉庫費用 :倉庫iから店舗jの輸送費用
85. 85 ©BrainPad Inc. Strictly Confidential 最後に、決定変数や目的関数が満たすべき制約を表した制約条件を決めます 例題 | 定式化 解説（3/3）制約条件を決めよう あなたはメーカーの物流担当者で、 倉庫から製品を店舗に配送しようとしています。 契約可能な倉庫は5つあり、契約すると倉庫費用がかかります。 どの倉庫を契約し、どれだけ配送すると、 倉庫費用と輸送費用を最小化できるでしょうか？ ただし、倉庫と店舗に次の条件がある。 1. 倉庫から配送する製品は倉庫容量以下となる。 2. 店舗の需要を満たすように配送する。 3. 配送費用は工場と店舗間で製品を1単位運ぶと発生する。 問題文 考え方 • 今回の問題で満たすべき制約は2つある。 • 倉庫から配送する製品は倉庫容量以下 • 店舗の需要を満たすように配送する 𝑀𝑖 は倉庫iの容量。 倉庫iを使わない場合は、右辺が0となり 倉庫iから運ぶ量の合計が0となる
86. 86 ©BrainPad Inc. Strictly Confidential 得られた決定変数、目的関数、制約式を1つにすると下記の通りになります 例題 | 施設配置問題 解答 例題の定式化
87. 87 ©BrainPad Inc. Strictly Confidential 施設配置問題を実際に実装してみましょう 演習 例題の定式化
88. 88 ©BrainPad Inc. Strictly Confidential 施設配置問題を実際に実装してみましょう 演習 作業時間（10分） 分からない所などあったら、遠慮なく声をかけてください。 5分経過したらヒントを出します。
89. 89 ©BrainPad Inc. Strictly Confidential 研修の冒頭に見たスライドを覚えていますか？
90. 90 ©BrainPad Inc. Strictly Confidential 例題 | 最適化研修のチーム分け 問題文 あなたは最適化研修の講師を担当することになりました 各受講生33名には予め、最適化の経験(4段階)とPythonの経験(5段階)を答えてもらっています 研修のグループワークを行う上で、8グループにバランスよく受講生を割り当てるにはどうすれば良いでしょう か？ 与えられているデータ id name 最適化スキル Pythonスキル 1 A 3 2 2 B 2 2 … 受講生の集合 グループの集合 グループごとにスキルポイントを均等 に分けられた時の理想的な値
91. 91 ©BrainPad Inc. Strictly Confidential まず最低限の割り当てを行うことを考える、とりあえず目的関数はなしで制約条件を考えます 例題 | 定式化 解説(1/3) あなたは最適化研修の講師を担当することになりました 各受講生33名には予め、最適化の経験(4段階)とPythonの経験(5 段階)を答えてもらっています 研修のグループワークを行う上で、8グループにバランスよく受 講生を割り当てるにはどうすれば良いでしょうか？ 問題文 考え方 • 今回は決定変数を人iをグループgに割り当てるか否かとする • 今回39人を9グループに割り当てるので、各グループは4人か 5人となる • さらに各人に対していずれかのグループに割り当てられる制 約 id name 最適化スキル Pythonスキル 1 A 3 2 2 B 2 2 受講生の集合 グループの集合
92. 92 ©BrainPad Inc. Strictly Confidential 次にバランスの良い割り当てになるためにはどうすれば良いかを考えるます 例題 | 定式化 解説(2/3) 考え方 • 今回は各グループの経験値の総和 が均等に割り振った時の値(AvgPoints)に近くなるようにします • ↑だと実行不能になる可能性があるため条件を緩めます AvgPoints あなたは最適化研修の講師を担当することになりました 各受講生33名には予め、最適化の経験(4段階)とPythonの経験(5 段階)を答えてもらっています 研修のグループワークを行う上で、8グループにバランスよく受 講生を割り当てるにはどうすれば良いでしょうか？ 問題文 id name 最適化スキル Pythonスキル 1 A 3 2 2 B 2 2 受講生の集合 グループの集合
93. 93 ©BrainPad Inc. Strictly Confidential 次にバランスの良い割り当てになるためにはどうすれば良いかを考えます 例題 | 定式化 解説(3/3) 考え方 • この条件のもとで超過分+不足分の最小化を行います ハードな制約条件をソフトにする あなたは最適化研修の講師を担当することになりました 各受講生33名には予め、最適化の経験(4段階)とPythonの経験(5 段階)を答えてもらっています 研修のグループワークを行う上で、8グループにバランスよく受 講生を割り当てるにはどうすれば良いでしょうか？ 問題文 id name 最適化スキル Pythonスキル 1 A 3 2 2 B 2 2 受講生の集合 グループの集合
94. 94 ©BrainPad Inc. Strictly Confidential 例題 | 解答 ここまでの話を踏まえると以下のような定式化になります 研修を通して理解できるようになったでしょうか？ 集合 受講生の集合 グループの集合 問題 定数 ：受講生 i の最適化のスキル ：受講生 i のPythonのスキル ：全員のスキルの総和をグルー プ数で割った値
95. ©BrainPad Inc. Strictly Confidential ⑥実践演習
96. 96 ©BrainPad Inc. Strictly Confidential これまでで学んだ知識を総動員して実践演習を行います 最適化案件で必要なすべての部分を考える必要があり、かなり難易度が高いですが頑張りましょう 【実践演習】現実問題の定式化～問題解決まで 実践演習の範囲 現 実 問 題 最 適 化 問 題 計 算 結 果 問 題 解 決 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討
97. 97 ©BrainPad Inc. Strictly Confidential コンビニ食の献立最適化をテーマに実践演習を行います 実践演習課題 かつて関口さんの一週間のコンビニ食の献立を最適化す るという社内PJが存在しました 本日はこの社内PJの模擬体験を90分で行ってもらいます DOORS記事 関口さんnote 演習の進め方 1. 定式化の記述 実際のプロジェクトではヒアリングが発生しますが、今回は 自作自演でチームでお題を決めて定式化を行ってください ホワイトボードや手元の紙に定式化を書いてチーム外の人に も定式化を説明できるようにしてください 2. 最適化モデルの実装 演習で行ったようにPuLPを用いて実際にモデルの作成を 行ってください 実装担当の人を決めても、全員で実装しても構いません 3. 解の可視化 サンプルコードを参考に必要があれば改変して得られた解の 可視化を行ってください チームで考えた目的関数や制約条件がしっかり満たされてい るかの確認などを行ってください 4. モデルの修正・改良 得られた解を可視化して解に違和感がある場合はモデルの改 善を行いましょう 納得のいく解が出た場合は1週間分の献立に拡張やまだ使っ てない情報を使うように改良などを考えてみてください
98. ©BrainPad Inc. Strictly Confidential ⑧今後学ぶと良いこと
99. 99 ©BrainPad Inc. Strictly Confidential ここまでお疲れ様でした！ 一日中講義、演習を行なってものすごく疲れたのではないかと思います。 今日は数理最適化入門として色々な話題について勉強してきましたが、”最適化を使う”ハードルは意外と低かったのでは ないでしょうか？ 汎用ソルバーを使うことで「裏側のどうやって解くか」を気にせずにすぐにビジネス課題をどう最適化問題に落とし込む かに集中することができます。 もちろん解けなかった場合の定式化のデバッグやアルゴリズムの設計が行いやすくなるので後々理論も勉強する必要があ りますが徐々に勉強していけば良いです。 最適化に対する敷居を高く思わずに、今日の実践演習のように身の回りの問題が最適化問題として定式化できないか？と いう視点を持っていただけるようになれば幸いです。 はじめに
100. 100 ©BrainPad Inc. Strictly Confidential 典型問題は「青チャート」みたいなもので、典型問題を組み合わせることで多くの問題は定式化できます 以下に参考書籍をいくつか紹介します 今後勉強すると良いと思うこと : MIPで典型問題を学ぶ DS新卒勉強会の指定書籍。 実務において役立つモデリ ングや考え方が多く載って いる 典型問題の実装方法と定式 化に関するさまざまなコツ を紹介してくれる本 混合整数計画問題へのモデ リングがかなり詳しく載っ ている Pythonではじめる数理最適化 あたらしい数理最適化 Python言語とGuroiで解く Model Building in Mathematical Programming
101. 101 ©BrainPad Inc. Strictly Confidential  MIPでの定式化に慣れてくると、なんでも定式化・最適化できるのでは？という気持ちになってきます ただそれは気のせいです. . .  実務で最適化を行う場合には「定式化はできるのだが大規模すぎて汎用ソルバーで問題が全然解けない」といった状況 はよく起こります  その場合に「汎用ソルバーに頼らずに自分でアルゴリズムを書く」という選択肢を最終手段として持っておけると非常 に強いです 今後勉強すると良いと思うこと : ヒューリスティクスアルゴリズムを学ぶ Atcoder Heuristic Contest https://www.terry-u16.net/entry/ahc001 より引用 広告配置を題材とした長方形詰め込み問題 など、実務に近い問題が出題されています BrainPadプログラミングコンテスト2025（AtCoder Heuristic Contest 046）より引用
102. 102 ©BrainPad Inc. Strictly Confidential ここまでPuLP+Cbcを使ってMILPを解く話をしてきましたが、MILPソルバー以外にも最適化ソルバーは存在します 例としてCbcなどをはじめとするMILPソルバーとは異なるアルゴリズムで実装されたOR-ToolsのCP-SAT Solverなどが あります こちらのソルバーは非線形な目的関数も扱える代わりに決定変数は整数変数のみとなっていますが、論理式に関して柔軟 なモデリングが可能です 今後勉強すると良いと思うこと : 他のモデラー・ソルバーの使い方を学ぶ https://developers.google.com/optimization/cp/cp_solver のサンプルコード →not equalのような論理制約をモデリングすることができます
103. 103 ©BrainPad Inc. Strictly Confidential 今日はnotebook上で最適化モデルを作って計算を行いましたが、実際の案件で最適化モデルを使うのはプログラミングを 知らないお客さんであることが多いです さらに最適化条件を色々変えて最適化問題を解くことを考えると、最適化のモデルをWebアプリケーションにのせて提供 することが望ましい場合があります 今後勉強すると良いと思うこと : Webアプリケーションを学ぶ BrainPad FASTというソリューションを展開しています https://www.brainpad.co.jp/services/professionals/bp-fast.html
104. 株式会社ブレインパッド 106-0032 東京都港区六本木三丁目1番1号 六本木ティーキューブ TEL：03-6721-7002 FAX：03-6721-7010 www.brainpad.co.jp info@brainpad.co.jp 本資料は、未刊行文書として日本及び各国の著作権法に基づき保護されております。本資料には、株式会社ブレインパッド所有の特定情報が含まれており、これら情報に基づく本資料の内容は、貴社以外の第三者に開示されること、また、本資料を評価する以外の目的で、その 一部または全文を複製、使用、公開することは、禁止されています。また、株式会社ブレインパッドによる書面での許可なく、それら情報の一部または全文を使用または公開することは、いかなる場合も禁じられております。 ©BrainPad Inc.
105. 105 ©BrainPad Inc. Strictly Confidential [外部公開用_202508_数理最適化研修のコード（例題・類題のみ） - Google ドライブ] https://drive.google.com/drive/u/1/folders/1fQJ_3irJA8eMTEUWAls-mj1ApX_Bntmh Appendix.