数理最適化と機械学習の融合

兵庫県立大学情報科学研究科 第一回 数理最適化データサイエンス研修会

「数理最適化と機械学習の 融合」
講師紹介
久保幹雄 東京海洋大学教授
所属:東京海洋大学大学院 海洋工学系 流通情報工学
専門と略歴
専門は,サプライ・チェインならびに組合せ最適化,
早稲田大学理工学研究科修了,博士(工学).早稲田大学助手,東京商船
大学助教授,ポルト大学招聘教授などを歴任. MOAI Lab CTO, A*
Quantum Director, Optimind Adviser を兼任。

Transcript

1. 数理最適化と機械学習の融合 Mikio Kubo
2. ⾃⼰紹介 久保 幹雄 東京海洋⼤学 教授 流通情報⼯学 サプライ・チェイン最適化⼯学 株式会社 モアイ・ラボ 取締役 CTO 株式会社 エー・スター・クォンタム 取締役 株式会社 オプティマインド アドバイザー https://www.youtube.com/@kubomikio https://x.com/MickeyKubo https://www.facebook.com/mikio.kubo.737 https://www.logopt.com/kubomikio/
3. 数理最適化と機械学習の融合 機械（深層）学習 LLM/AGI 実際問題 数理最適化 (MO) 最適化 ⼈⼯知能 (AI) メタヒューリスティクス
4. 略語と分類
5. 略語と分類 • MO：数理最適化 (Mathematical Optimization) • O：より広い最適化（Optimization) • ML： 機械学習（Machine Learning) • RL：強化学習（Reinforcement Learning） = O + ML • MPC：モデル予測制御 (Model Predictive Control) = O + ML MOとMLの融合 Þ 7 つのパターンに分類 1. ML -> MO (ML-first MO-second: ML先 MO後) 2. MO -> ML (MO-first ML-second: MO先 ML後) 3. MO ⊃ ML (ML assists MO, ML4MO: 機械学習が最適化をアシスト） 4. ML ⊃ MO（MO assists ML, MO4ML: 最適化が機械学習をアシスト） 5. 最適化の基礎理論で相互乗り⼊れ 6. RL/MPC中⼼の融合型（ML & MO assists RL/MPC) 7. ⼤規模⾔語モデル (LLMs）でモデリング（とUI⽣成）をアシスト
6. 融合パターンの概念図 ML MO ML -> MO (ML-first MO-second: ML先 MO後) MO -> ML (MO-first ML-second: MO先 ML後) ML MO MO ⊃ ML (ML assists MO, ML4MO） ML ⊃ MO（MO assists ML, MO4ML） 最適化の基礎理論で相互乗り⼊れ RL/MPC中⼼の融合型 MO ML MO ML ML MO ML MO RL/MPC LLMs assist MODELING ML MO MODELING LLM
7. パターン１ ML → MO ML MO
8. パターン１ ML → MO MLをした後で MO を適⽤する 最も古典的で⾃然な（予測をしてから最適化）アプローチ 1. MLで予測し関数近似 => 近似した制約や⽬的関数をMOで解く ü MLの予測モデルをそのままMOに数式として埋め込む（Gurobi 10.0+) ü MLをブラックボックスとして最適化 ü MLの予測モデルを現実的な仮定でMOで解きやすい関数として近似 2. MLで前処理（e.g., クラスタリング） → MO ML MO データ 解
9. 古典的な予測後最適化の問題点と解決法 • 誤差の少ない予測は必ずしも良い解に結びつかない => Smart Predict-then-Optimize (MLの中で最適化；最適値との 差（の近似）を損出関数とする） • 回帰は点推定 => パラメータの分布を推定（Estimate-then- Optimize) + 確率的最適化 • ⽂脈から問題例の分布を推定 => 分布的ロバスト最適化 ML 分布的 ロバストO データ +⽂脈 解 問題例 （の分布）
10. パターン2 MO → ML ML MO
11. パターン2 MO → ML • 最適化をした後に機械学習をする • 例：過去の顧客需要が既知の配送最適化 ü 過去のデータで最適化を⾏い，各⽇に対する最⼩のトラック台数を求める ü 過去の⽇情報などを特徴として，トラック台数を予測する回帰モデル ML MO データ 解
12. パターン3 MO ⊃ ML MOタスクが中⼼ ML4MO MO ML
13. パターン3 MO ⊃ ML, ML4MO MLがMOをアシスト（⽬的は最適化） 1. MLで解法の選択，解法の（ハイパー）パラメータの設定・アルゴリズムの 選択 2. 最適化の内部でML ü 分枝ルール・切除平⾯をML（RL）で改善 3. 強化学習で組合せ最適化 4. MO でたくさんのデータ（問題例と解の組）を⽣成し，MLで訓練 新しい問題例に対してMLを⽤いてMOを⾼速化 ü MLが解のヒントや満たすべき制約を返し，MOを⾼速化 (MIPlearn) ü MLが近似（実⾏不能）解を返し，近い実⾏可能解に変換（optimization proxy) ü MLが整数変数の値と等号が成⽴する不等式制約を返し，そこから解を⽣成 (optimization voice) MO ML
14. ML4MOの分類 問題例 解 ML MLが解を返す （訓練データを作るためにMOを利⽤） MO 問題例 解 ML パラメータ アルゴリズム 最適化の前にML MO 問題 例 解 ML 最適化の内部にML 問題例 解 RL RLで組合せ最適化問題を解く
15. パラダイムシフト すべての問題例の集合 実際の問題例の集合 すべての問題例に対して ⾼速に誤差の⼩さい解を⽣成する ことは（おそらく）できない たくさんの過去の 実際の問題例 過去のたくさんの実際問題の 問題例と対応する解がある 対応する解 NP-困難性 すべての問題例の集合 機械（深層）学習の利⽤ ?
16. NP-困難性の克服 低速 ⾼速 Speed 厳密解（誤差⼩） Error Exact solution methods Greedy Local Search Metaheuristics MOAI (機械学習+数理最適化） ⼤規模インスタンスに対する 誤差の⼩さい解を⾼速計算 + （近似解）誤差⼤
17. MIPLearn, Optimization Proxies and Voice 機械学習 問題例 MIPLearn 数理最適化 解 解のヒント 問題例 Optimization Proxies 修復（層） 解 実⾏不能近似解 （プロキシ） 機械学習 問題例 線形⽅程式系求解 解 整数変数の値 等式になる不等式制約 Optimization Voice 深層学習 問題依存 連続変数のみ 問題依存（整数変数のみだと✘；不等式制約が少ないと✘） 問題依存 数値のみ変化（構造は同⼀） 数値のみ変化（構造は同⼀） 数値のみ変化（構造は同⼀） +制約をラグランジュ緩和 動機：解を直接 ML で出すのは難しい
18. ⼀般化：エンコード・デコード法 機械学習 問題例 デコーダー 解 解のエンコーディング 例：スケジューリング問題 作業の投⼊順（半順序）＋作業のモード : デコードはアクティブスケジュール⽣成スキーム 作業の投⼊順（半順序） : デコードはスケジューリング最適化 OptSeq 例：配送計画問題 事前巡回路 （デコードは動的最適化） 運搬⾞への割当（柔軟性のための重複あり）+ 事前巡回路（デコードはリコース戦略） エンコーディングを解に ⾼速に変換するアルゴリズム エンコーディング デコーダー MIPlearn 付加される制約 MIPソルバー Opt. Proxies （実⾏不能）解 修復層 Opt. Voice 等号制約，整数変数 連⽴⽅程式 エンコーディングの複雑度 << 解の複雑度
19. ML4MOの課題 • 訓練⽤の問題例とテスト⽤の問題例が「近い」必要がある • 問題例の構造が同じで数値だけ異なる場合に有効（ほとんどの研 究がこれ） • 多くの数値実験では，「似た」問題例を⼈⼯的に⽣成し，評価 • 現実問題に対するものは少ない（電⼒への応⽤が例外） • 構造が異なる問題例に対しては「近さ」の定義が必要 （輸送問題を解くことによる「問題例の近さ」の計算）
20. 配送最適化への適⽤ • SOTA: PyVRP (Genetic Hybrid) • 点数 275 のベンチマーク問題 • 5000反復 800秒 • 位置と需要量ランダム • 過去の「近い」40の問題例の集団を初期集団として 利⽤ => 10反復 （1秒以下）で40000反復と同等
21. パターン4 ML ⊃ MO MLタスクが中⼼ MO4ML ML MO
22. パターン4 ML ⊃ MO, MO4ML • MLのタスク（分類，回帰）を(M)Oで⾏う • 制約付きのML => 最適化で求解（凸最適化なら簡単） • 特徴選択のためのMOモデルや最適決定⽊のためのMOモデル • 制約付きMLモデルのための最適化⼿法の適⽤（e.g., Lagrange緩和） MO データ 分類 回帰 ML MOがMLをアシスト（⽬的は機械学習）
23. MO4MLの問題点 • MOをそのまま使うと計算量⼤ • カテゴリーデータに対する⾼速化⼿法はあるが，連続データに は適⽤しにくい（離散化が必要）
24. パターン 5 最適化の基礎理論レベ ルでの相互乗⼊れ MO ML
25. パターン 5 最適化の基礎理論レベルでの相互乗⼊れ • 異なる分野として研究されているが，本質的な⽬標は同じ ü 深層学習(DL)の最適化（⾮凸最適解）->慣性項 Adamやfit-one cycleなどの実験に基づく改良 ü 微分不可能関数の最適化（劣勾配法） -> Nesterovの加速 理論的な収束性の証明 ü 実験的に良いDLの⼿法を最適化問題の（不安定な）劣勾配の代⽤とし て使う • 機械学習のモデルの数学的解釈としての数理最適化 ü 定式化から疎性を組み込んだMOモデル（e.g., 回帰，SVM，NN） ü モデルに対する洞察 -> 改良や収束性の保証 ü 新しいモデルのヒント
26. パターン6 動的モデ ルに対する融合型 ML MO RL/MPC
27. パターン6 動的モデルに対する⼿法 動的計画(DP) 近似DP (ADP) RL MPC MO Hybrid モデル あり あり なくても良い あり あり 予測 なし なし なし 過去の状態から 予測 過去の問題例と⽂ 脈から問題例の分 布を予測 価値関数 あり ⾏動後状態に対 して定義 あり あり ⾏動後状態と⾏動 前状態に対して定 義 最適化 基本は貪欲 1期の最適化 基本は貪欲 Tree Search， Beam Search, Rolloutを併⽤ 有限期間の最適 化をローリン グ・ホライズン 2次の⾮線形 有限期間の問題を (M)Oで最適化 分布的ロバスト最 適化 価値関数の近似 の⼯夫 状態の特徴に対 する区分的線形 関数で近似 区分的線形，NN， 決定⽊をMOに組み 込む
28. MO Hybrid Solution Period Instance 𝑡 − 1 𝑡 𝑡 + 1 𝑡 + 2 ⋯ 𝑇 𝑇 + 1 ⋯ (𝐼! "!#, $ 𝐼!$% "!#, $ 𝐼!$& "!#, … , $ 𝐼' "!#) (𝑋! "!#, 𝑋!$% "!#, 𝑋!$& "!#, … , 𝑋' "!#) Encode & Decode 予測 問題例⽣成 ($ 𝐼!$% , $ 𝐼!$& , … , $ 𝐼' , ⋯ ) 𝐼( (𝑖 = ⋯ , 𝑡 − 1, 𝑡) (𝑋( "(#, 𝑋($% "(#, 𝑋($& "(#, ⋯ ) (𝑖 = ⋯ , 𝑡 − 1) (𝐼( "(#, $ 𝐼($% "(#, $ 𝐼($& "(#, ⋯ ) 𝑆( V 𝑆( 𝑚𝑎𝑥 𝑣 𝑥 + 𝑉 𝑆'$% 𝑋! "!#, 𝑋!$% "!#, 𝑋!$& "!#, … , 𝑋'(% "!# ≈ 𝑋! "!(%#, 𝑋!$% "!(%#, 𝑋!$& "!(%#, … , 𝑋'(% "!(%# 状態 価値関数 RL MPC 過去の問題例と 解の組 （訓練データ）
29. パターン 7 LLMs assist MODELING ML MO MODELING LLM
30. エージェントAIで数理最適化問題のテキス トをモデル・プログラムに変換 • 数理最適化問題を定式化してコードにするのが実際問題解決の ボトルネックになっている • これをLLM（⼤規模⾔語モデル）でできたら嬉しい • LLMの進展により練習問題程度ならほぼほぼ成功 • 複数のエージェントとツール（コードの実⾏）を使うともっと 良い（UIまで⽣成可能） • AMPLを利⽤すると成功確率上昇 (AMPLは古くからある数理最適化モデリング⾔語； 2025年からMOAI Labが国内総代理店)
31. AGI4OPT In the context of manufacturing planning, we tackle the Capacitated Multi-level Lot Sizing Problem with Backlogging. We make the following assumptions in defining and formulating this problem. First, we assume that setup times and costs are non-sequence dependent, setup carryover between periods is not permitted, and all initial inventories are zero. Second, all production costs are assumed to be linear in production output and do not vary over time; hence, they can be dropped from the model for simplicity. Setup and holding costs also are assumed not to vary over time. Furthermore, end items are assumed to have no successors, and only end items have external demands and backlogging costs. Finally, we assume zero lead times and no lost sales. Modeling Agent Ampl model UI Agent Web app
32. AGI4OPT 4作業3機械のスケジューリング問題を考える． 各作業はそれぞれ 3つの⼦作業（これを以下では作業とよぶ）から成り, この順序で処理しなくてはならない． 各作業を処理する機械, および処理⽇数は，Excel dataで与えられている．⽬的は 最⼤完了時刻最⼩化とする． ここでは，さらに以下のような複雑な条件がついているものと仮定する．各作業の初めの 2 ⽇間は作業員資源を必要とする操作がある．この操作は平⽇のみ, かつ 1⽇あたり⾼々2個しか⾏うことができない．各作 業は，1⽇経過した後だけ，中断が可能．機械1での作業は，最初の1⽇は2個まで並列処理が可能．機械2に限り, 特急処 理が可能．特急処理を⾏うと処理⽇数は4⽇で済むが, 全体で1度しか⾏うことはできない．機械1において, 作業1を処理 した後は作業2を処理しなくてはならない Modeling Agent OptSeq model UI Agent Web app
33. 最適化の普及のために MOAI Lab + 数理最適化データサイエンスセンター
34. MOAI = Fusion of Three Fields Mathematical Optimization Metaheuristics Machine Learning Deep Learning LLMs MOAI Hierarchical building block AutoOpt Math-heuristics Distributionally robust optimization Encode-decode method MO hybrid for dynamic stochastic models End-to-end learning Supply chain modeling language Modeling and app generation with agentic LLMs (AGI4OPT) Automatic decomposition Instance similarity
35. 最適化による実際問題の解決フロー (Usual Approach) ヒヤリング モデル作成 PoC 評価 モデルを⼀から作成 特定の解法で⼀から作成 動かない 条件不⾜ メトリクスが悪い 数理最適化で定式化 + Solver AIアプローチ（アルゴリズムを設計） PoC（プロトタイプ作成）の無限ループ
36. MOAI Approach ヒヤリング 典型問題 関連研究を調査済み 問題タイプ別にSOTA解法の準備とライブラリ化 ベンチマーク問題例でのテストと評価 SOTA解法の融合による最先端⼿法の開発 MOAI Platform カスタムモデル + 開発 + 評価 導⼊
37. MOAIソリューション • サプライチェーン ü ロジスティクス・ネットワーク設計 ü サプライチェーン・リスク分析 • 需要予測・在庫コントロール ü 深層（機械）学習による需要予測 ü 動的在庫コントロール ü 動的価格付け • ⽣産計画 ü 安全在庫配置 ü ロットサイズ ü スケジューリング • 輸配送計画 ü サービス・ネットワーク設計 ü 配送計画 ü 船舶スケジューリング 個々のモジュールをSCML (Supply Chain Modeling Language) で有機的に結合
38. MOAI サプライチェーン・ソリューション Logistics Network Design Safety Stock Allocation Lot-sizing Scheduling Multi-period Vehicle Routing Ship Scheduling Inventory Vehicle Routing Demand Forecasting Machine (Deep) Learning End-to-End Learning Dynamic Inventory Control Dynamic Pricing Supply Chain Risk Analysis Plant DC Demand Point Supply ⽣産計画 輸配送計画 需要予測・在庫コントロール
39. MOAI ⽣産計画ソリューション Bill Of Materials Safety Stock Allocation Lot-sizing Scheduling Inventory Push Pull Boundary Customer demand Guaranteed Lead Time 単なるスケジューラー（処理的IT）ではなく，複数の最適化技術を融合 安全在庫配置モデル （⼀般有向グラフ10000点を最適化）
40. MOAI ⽣産計画ソリューション Bill Of Materials Safety Stock Allocation Lot-sizing Scheduling 4 6 3 7 8 1 3 5 4 2 5 20 21 7 demand production 16 10 7 0 13 12 9 4 0 5 0 inventory 容量制約付きロットサイズ最適化モデル （ERPの⼭崩しヒューリスティクスを3割以上改善）
41. MOAI ⽣産計画ソリューション Bill Of Materials Safety Stock Allocation Lot-sizing Scheduling Resource Network Ganntʼs Chart スケジューリング最適化モデル （10万以上のタスクを最適化）
42. MOAI 輸送ネットワーク・ソリューション Service Network Design Multi-period Vehicle Routing Ship Scheduling Inventory Vehicle Routing 10000地点×30⽇分の配送最適化
43. MOAI Lab • ⾼度な専⾨知識を有する専⾨家による最新の最適化アルゴリズム（数理最適化，メタ ヒューリスティクス，機械学習の融合） • サプライチェーン全体を網羅する最適化技術とSCMLによる統合 • 実証データ：⼤規模問題例に対する⾼速解法 （e.g., 10万タスクのスケジューリング，3万地点の配送計画） • ロードマップ 1. 常に最⼤規模の問題例を最速で最適化する技術を維持 2. ユーザーの実データの蓄積によるMOAI技術のロバスト化（単にベンチマーク問題例を解く のではなく，実際のデータの特徴を⽣かした最適化） 3. 複数の解法を準備し，⾃動的にユーザーにとって最適なものを選択する⾃動最適化 (AutoOpt) 技術の開発 4. Agentic AIを⽤いて，ユーザーのヒヤリングとデータから⾃動で最適化システムを構築する (AGI4Opt) の開発
44. おわりに
45. おわりに • MO+MLの分類の提案（完全な分類ではなくあくまで便宜的） • MO+MLの研究は急速に拡⼤ • 様々な分野で独⽴に研究 • 今後は，分野を超えた交流が必要 • 毎⽇，最適化問題を繰り返し解いている実務家の⽅は，問題例と 解の組をたくさん保管しておいてもらえると嬉しいです • MOAI Labの紹介と今後の展望