白金鉱業Meetup Vol.16_数理最適化案件のはじめかた・すすめかた

2024年12月11日に実施した、白金鉱業 Meetup Vol.16@六本木（数理最適化）でのブレインパッド羽田の登壇スライドです。

イベントURL
https://brainpad-meetup.connpass.com/event/335599/

羽田 X/Twitterアカウント
https://x.com/H_A_ust

Transcript

1. 数理最適化案件のはじめかた・すすめかた 2024年 12月11日
2. ©BrainPad Inc. Strictly Confidential 2 自己紹介 羽田充宏（はだあつひろ） ◦ 新卒2年目データサイエンティスト ◦ だーはー(@H_A_ust)/X • 学生時代の研究 ◦ 大阪大学情報科学研究科情報数理学専攻卒業 ◦ 機械学習と微分方程式、データ同化、Neural ODEなどの研究をしていました • 入社から経験した案件 ◦ 2023年7月〜2024年3月 : 食品メーカー様向け生産計画最適化webアプリケーション作成 ◦ 2024年4月〜 : toC企業様向け戦略策定支援 minimize subject to 𝐿(𝑥(𝑡𝑓 )) 𝑑 𝑑𝑡 𝑥 𝑡 = 𝑓(𝑥(𝑡)) 𝑥 𝑡0 = 𝜃 𝑥: 𝑡0 , 𝑡𝑓 → ℝ𝑑, 𝐿: ℝ𝑑 → ℝ, 𝑓: ℝ𝑑 → ℝ𝑑
3. ©BrainPad Inc. Strictly Confidential 3 1. 最適化案件のはじめかた ⚫ 最適化案件のながれ ⚫ 定式化 ⚫ 最適化問題を解く ⚫ 解の確認・定式化の修正 2. 最適化案件のすすめかた（Pythonではじめる数理最適化第5章を例に） ⚫ 問題設定 ⚫ PoCにおける最適化システム ⚫ 環境構築 ⚫ データまわりの設計 ⚫ 最適化モデルの実装 今日話すこと 二年間のDSとしての経験を振り返って、入社直後の自分に伝えたい内容を詰め込みました 2024/03/23 (株)オーム社発刊
4. ©BrainPad Inc. Strictly Confidential 最適化案件のはじめかた ~最適化案件とは何かを知る~
5. 5 ©BrainPad Inc. Strictly Confidential 最適化案件は概ね以下の一連の手続きからなると思います。 定式化がアルゴリズムが一発で決まることは稀でお客さんのフィードバックをもらいながら何回もサイクルを回します。 最適化案件のながれ 現 実 問 題 最 適 化 問 題 計 算 結 果 問 題 解 決 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討 https://zenn.dev/umepon/articles/50a74c75f32096875d94 を参考に作成
6. 6 ©BrainPad Inc. Strictly Confidential 最適化案件のながれ | 定式化 現 実 問 題 最 適 化 問 題 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討 まず初めに現実問題を数式を使って最適化問題として記述する必要があります。 目的関数： 最大化・最小化 したい指標 決定変数： 最適化により決 定したい値 制約式： 指標の最適化に あたっての制約 生産スケジュールの作成を自動 化したい。 製品の数は〇〇で各商品に対し て△△の条件を満たす必要があ り…、××のあとは□時間イン ターバルを空ける必要があり… 定式化 ※定式化イメージ
7. 7 ©BrainPad Inc. Strictly Confidential 最適化案件のながれ | 最適化問題を解く 現 実 問 題 現実問題を最適化問題として記述できれば、その問題をどう解くかに専念することができます。 最適化問題を解くアプローチとしては大きく以下の２通りに大別されます。 (1)汎用ソルバーによる解法 幅広い問題に対して適用可能なアルゴリズムを予め実装 したソフトウェアを利用する方法 制約条件の変更が生じても比較的変更が容易 (2)フルスクラッチアルゴリズムによる解法 自分で1から求解アルゴリズムを実装する方法 問題固有の性質を使うことができるので求解性能は高い 一方で保守性が低くなりやすい 求 解 性 能 汎用性 (1)汎用解法 (2)フルスクラッチ それぞれのアプローチには 性能・汎用性についてのトレード オフが存在する 案件ではソルバーが使われること が多い 最 適 化 問 題 計 算 結 果 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討
8. 8 ©BrainPad Inc. Strictly Confidential 最適化案件のながれ | 解の確認 ・ 定式化の修正 考えた定式化が一発でうまくいくことはまずあり得ません。 最適化問題の定式化やアルゴリズムを見直しながら改善を繰り返します。 ソルバーやアルゴリズムによって解を得た後は結果を可 視化を行います 生産計画における生産順番を表すガントチャート可視化の例 工場の設備上、製品Aの次に製品B を生産することはできません 定式化の修正 ⋮ 部分的な修正で良いこともあればモデルの 大部分を変更しなければならない破滅的変更を 伴う場合もあります 現 実 問 題 最 適 化 問 題 計 算 結 果 問 題 解 決 定式化 アルゴリズム or ソルバー による求解 得られた解の 可視化・確認 最適化問題とアルゴリズムの再検討
9. ©BrainPad Inc. Strictly Confidential 最適化案件のすすめかた ~具体的にどう実装したらよいかを知る~
10. 10 ©BrainPad Inc. Strictly Confidential 本発表では「Pythonではじめる数理最適化」の第5章を題材にして具体的な最適化案件のシステム実装方法について説明 します。第5章では下記のような1車両を用いた多期間の配送計画を扱っていました。 問題設定概要 デポ お店1 お店2 お店3 荷物 店舗 重さ[kg] 指定期間 荷物1 お店1 1,000 [1-2] 荷物2 お店1 1,000 [1-2] 荷物3 お店2 1,000 [1-2] 荷物4 お店3 2,000 [1-2] 注文リスト ざっくり問題設定： 注文リストに従って複数日の配送計画を考える 自社配送できない場合はある注文を外注することもできる 最終的には各荷物をいつ、どの順番で運ぶか、外注するかを 考える 目的関数： • 自社ドライバー残業費+外注費の最小化 • 総移動時間の最小化 • … 制約条件： • 最大残業時間制約 • トラックの積載量制約 • 荷物を指定期間内に配送する制約 • … 一日目の配送例
11. 11 ©BrainPad Inc. Strictly Confidential この配送計画のPoCで前述のサイクルを回すために下記のような最適化システムを構築したいとします。 PoCにおける最適化システム クライアントから データ受領＆入力 入力データ の処理 最適化モデ ルの作成 ソルバーに よる求解 出力データ の処理 クライアントによる 出力結果確認 最適化システム
12. 12 ©BrainPad Inc. Strictly Confidential この配送計画のPoCで前述のサイクルを回すために下記のような最適化システムを構築したいとします。 本発表では下記のツールを使ってどうやってこのシステムを実装するかについてお話します。 PoCにおける最適化システム クライアントから データ受領＆入力 入力データ の処理 最適化モデ ルの作成 ソルバーに よる求解 出力データ の処理 クライアントによる 出力結果確認 最適化システム Dev Containers MkDocs 環境構築 データ回り https://github.com/h-atsu/shirokane_meetup_opt 本日説明する内容のコード
13. 13 ©BrainPad Inc. Strictly Confidential Dev ContainerとはVS Codeの拡張機能の一つで、定義ファイルを用意するだけでDockerを利用してVS Code上の開発 環境（拡張機能もふくめてまるっと）を作成することができます。 環境構築 | Dev Containerによる開発環境 最適化における環境構築のつらみ： • Appleシリコンのpython-mip使ってCbc呼び出すの が難しい • 開発している人によって使ってるソルバーのバー ジョンが違う • … devcontainer.jsonを用意するだけ*で手軽に 開発者全員の環境を揃られる！ 使用イメージ VS Codeの設定 環境変数の設定 ビルド時のコマンド ここにソルバーインス トール設定などを記載 *ソルバーのインストールなどは別途postCreateCommandに登録しておく DockerFileやDocker Composeを使って環境構築することもできる
14. 14 ©BrainPad Inc. Strictly Confidential 使い方も簡単で”Reopen in Container”のボタンをクリックするだけで手軽に使い始めることができます。 例として下記レポジトリに「Pythonではじめる数理最適化」の開発環境を作成しています。 これを使えばMacでもWindowsでもワンクリックでpython-mip, Cbc, CVXOPTを使い始めることができます。 環境構築 | Dev Containerによる開発環境 設定ファイルがあるとVS Code起 動時にポップアップがでる* *コマンドパレットからも呼び出し可能 https://github.com/h-atsu/PyOptBook コンテナの作成や各種ソルバーの インストールが行われる
15. 15 ©BrainPad Inc. Strictly Confidential 下記のようなディレクトリ構成にしておくと実装の見通しがよくなります。 環境構築 | ディレクトリ構成 data/ outputs 最適化結果を格納 raw 受領データを格納 docs/ 定式化に関わるドキュメント data_processor/ データ入出力に関わるコードを格納 models/ 最適化を行うクラス optimize_dataclass/ データクラス scripts/ 最適化計算をまわすコード 基本的な思想： • src/配下 • 前述の最適化システムを構成するコードを書く • notebook/配下 • アドホックな分析コードを書く • 例えばPoC初期フェーズにおけるモデル作成＆ 検証はこのディレクトリに書き殴るなどの使い 方を想定(徐々にsrc/へ清書するイメージ) • システムができた後においてもdata/outpus配 下に出力された結果のアドホックな分析を行う notebook/ アドホックな分析コードを格納 これらの考え方は下記の記事の思想に従っています https://qiita.com/suikabar/items/f713412977743e08d5bf src/ 整備されたコード
16. 16 ©BrainPad Inc. Strictly Confidential 最適化案件では定式化をドキュメント化してチームメンバーと共有する必要があります。 MkDocsというPythonライブラリを使うとMarkdownで書いた定式化をHTMLドキュメントとして確認できます。 環境構築 | MkDocsによる定式化共有環境 このように左にエディタ、右にプレビューという形で 定式化のドキュメントを作成することができます MkDocsの嬉しさ： • Markdownで管理できるのでgitで定式化も バージョン管理できる(パワポだとつらい) • 静的サイトジェネレーターのため適当な場所 にデプロイして定式化を共有できる • 左のMaterialテーマなど様々な見栄えの良い テンプレートが存在する • Copilot等のコーディング支援ツールを使っ て効率的にドキュメント作成できる* *本当はコードからLLMで定式化自動生成とかできると嬉しい
17. 17 ©BrainPad Inc. Strictly Confidential 開発初期段階ではnotebook形式でモデルを書きたい、けどgit管理できなくて辛いみたいな状況はあるかと思います。 そんな時はVS Code機能のPython Interactive Windowを使うとgit管理しつつnotebookを書くことができます。 (余談) 環境構築 | Python Interactive Window Python Interactive Windowの嬉しさ： • .pyスクリプトなのでgit管理しやすい • Copilot等のコーディング支援ツールの 恩恵を受けれる • PDFやHTMLでエクスポートすること ができる（notebookをレポートとして 使っていた人も今まで通り使える！） “# %%”で囲ったコードが 一つのセルとして認識される 右側に出力結果があらわれる 実行中の変数を確認できる
18. 18 ©BrainPad Inc. Strictly Confidential PoCにおいてはエクセルを最適化システムのInput/Outputインターフェースとするのがおすすめ*です。 入出力のエクセル定義書やデータ例を作成すると、クライアント側にも何を入力として準備する必要があって、何が出力 として得られるのかを具体的にイメージしてもらいやすくなります。 データまわりの設計 | エクセルによる入力・出力フォーマット定義 入力データ定義 (注文データ定義の例) 出力データ (日毎計画出力の例) 〇〇のデータはすぐに用意 できるが、△△のデータは 社内で取りまとめる必要が あるので準備に時間がかか る… など 実際の計画業務においては ××の観点も考慮している のでその可視化もみてみた い… など *本番運用に移行する際には基幹システムのrawデータ→入力データ定義のフォーマットに変換する必要がある 具体的な形で見えると コミュケーションが円滑になる
19. 19 ©BrainPad Inc. Strictly Confidential 題材の配送計画においては一例として下記のような入出力定義ができます。 データまわりの設計 | エクセルによる入力・出力フォーマット定義 入力データ定義 出力データ例 店舗マスタ 注文マスタ 日毎の計画 注文毎の計画 最適化結果サマリ
20. 20 ©BrainPad Inc. Strictly Confidential エクセルによる入力定義を定めても、フォーマット通りに入力が行われないケースはしばしばあります。 DataFrameバリデーションツールのpanderaを用いることで入力データのバリデーションを行うことができます。 データまわりの設計 | Panderaによる入力データのバリデーション データモデルの定義 loaderの定義 Panderaの嬉しさ： • loaderを使っている限り想定したDataFrameが読み 込まれているという安心感 • 基本的に入力エクセルのシートと対応しているため、 入力データの定義をコード管理できる* "error in check_types decorator of function 'load_locations_mst': Column 'is_depot' failed validator number 0: <Check isin: isin([0, 1])> failure case examples: [{'is_depot': 2}]" 使用例 bool値の制約違反 どこで何のエラーが出たか教えてくれる *一方で前述の入力データ定義書エクセルと二重管理になっている部分があり辛いとも思える。。。
21. 21 ©BrainPad Inc. Strictly Confidential システム全体の入出力は先程エクセルで定義しましたが、それとは別に最適化モデルに渡すためのデータクラスを設計し ておくと見通しが良くなります。 データまわりの設計 | 最適化のための入力、出力、設定データクラス システム全体像 最適化モデル 入力エクセル 最適化入力 データクラス 最適化設定 データクラス 出力エクセル 最適化出力 データクラス 解の可視化 基本的な思想： • 最適化入力データクラス • エクセルで受け取ったマスタ情報をもとに最適 化モデルが使いやすいように加工を行ったデー タクラス • 最適化設定データクラス • データセット名、計算時間、使用する最適化モ デル、制約条件のON/OFFなどの情報を持った データクラス • 最適化出力データクラス • 出力エクセルや解の可視化を行いやすいように 最適化結果の情報を持たせたデータクラス このような設計にしておくと入出力の加工とモデリング を疎結合にすることができる 後述のように最適化モデルを複数試しやすくなる
22. 22 ©BrainPad Inc. Strictly Confidential run_optimize.py 最終的なデータフローは以下のようになります。 データまわりの設計 | 最適化のための入力、出力、設定データクラス システム全体像 最適化モデル model.py 入力エクセル 最適化入力 データクラス 最適化設定 データクラス 出力エクセル 最適化出力 データクラス 解の可視化(アドホック) execute_model.py 解の可視化(定型) notebook/で可視化 run_optimize.py：最適化計算の実行スクリプト execute_model.py：入力・設定データクラスから出力データクラスの変換 make_input_data.py：入力エクセルから入力データクラスの変換 write_output_data.py：出力データクラスから出力エクセルの変換 model.py：最適化を行うクラス write_output_data.py make_input_data.py
23. 23 ©BrainPad Inc. Strictly Confidential 以下は題材の配送計画におけるデータクラス設計の一例です。Python標準ライブラリのDataClassに変えて、Pydantic を用いるとpanderaと同様に型や制約を付けた堅牢なデータクラスを作ることができます。 データまわりの設計 | 最適化のための入力、出力、設定データクラス 最適化入力データクラス 最適化出力データクラス 店舗データクラス 注文データクラス 上記とその他集合 を束ねたデータク ラス 日毎の最適化結果 注文ごとの結果 上記とその目的関 数値を束ねたデー タクラス
24. 24 ©BrainPad Inc. Strictly Confidential 以下は題材の配送計画におけるデータクラス設計の一例です。 Pydanticを用いると堅牢なデータクラスを作ることができます。 データまわりの設計 | 最適化のための入力、出力、設定データクラス 最適化設定データクラス 目的関数 • 優先順位、ON/OFF、方向 制約条件 • ON/OFF 設定全体 • 対象データセット名 • 計算時間 • 計算スレッド数 • 入力定数 全体像（再掲） • 設定データクラスは最適化計算実行スクリプトの 入力となるので基本的には計算ごとに変えたいパ ラメータを保持させておく • そうすることで設定ファイルを変えるだけで • 計算時間を延ばしたら？ • 制約条件を緩めたら？ といったシミュレーションを行うことができる
25. 25 ©BrainPad Inc. Strictly Confidential 最適化モデルは以下のような基底クラスを考えると見通しがよくなります。 色々な定式化を考えて複数のモデルを作成するときもこのインターフェースを守れば同様に計算実行ができます。 最適化モデルのクラス設計 最適化モデル基底クラス モデル実行関数(execute_model.py)
26. ©BrainPad Inc. Strictly Confidential 26 まとめ 本日は最適化案件とは？から始まり、「Pythonではじめる数理最適化」第5章の内容を例に具体 的な実装方法などを話しました。 実案件においては他にもテストなど考えるべきことはたくさんあると思いますが、本発表が少し でも考え方の役に立つと幸いです。 Enjoy!
27. 株式会社ブレインパッド 106-0032 東京都港区六本木三丁目1番1号 六本木ティーキューブ TEL：03-6721-7002 FAX：03-6721-7010 www.brainpad.co.jp info@brainpad.co.jp 本資料は、未刊行文書として日本及び各国の著作権法に基づき保護されております。本資料には、株式会社ブレインパッド所有の特定情報が含まれており、これら情報に基づく本資料の内容は、貴社以外の第三者に開示されること、また、本資料を評価する以外の目的で、その 一部または全文を複製、使用、公開することは、禁止されています。また、株式会社ブレインパッドによる書面での許可なく、それら情報の一部または全文を使用または公開することは、いかなる場合も禁じられております。 ©BrainPad Inc.