seminar/2020/10/17/1240_OR-Tools - 豚吐露＠wiki

OR-Tools を使って数理最適化に触れてみよう／太田 満久(おおたまん)

2020-10-17(土) 13:20～14:00

Google OR-Tools
https://developers.google.com/optimization

数理最適化とは
Google Cloud Next
→機械学習がどのように活用されてるか？
　→機械学習だけで閉じる用途は無い
　　→AIの活用を語る上で必須の技術

成約を加味して最適な値を見つける手法
→在庫切れを加味しながら、売上を最大化したい。

数理最適化にはデータが必要
→AIブームのおかげでbigdataが蓄積され始めている
　→応用例：配送、資源割当、配合、販売、スケジューリング、拠点配置、ポートフォリオ選択、税収構成、与信信託、昨つけ、飼料配合、販売価格決定、検査機器の調整、配置転換、人員管理、リサイクル、予算配分

Google OR-Tools
https://developers.google.com/optimization/introduction/overview
→用途：配送計画、スケジューリング、ピンパッキング
→利用可能なソルバ：成約プログラミング、線形計画法、ルーティング、グラフ
→言語binding：C++、Python、Java、C#

ソルバー：任意の計算が可能な関数的、ライブラリ的なもの。様々な目的のソルバーがある。

数理最適化を使う
→①と②を繰り返す
　→①定式化(最適化モデルの修正)
　　→解きたい課題を最適化モデル(数理最適化問題)に落とし込む
　→②最適化計算
　　→数理モデルを解く。ソルバーを用いる。

①に数理最適化にGoogle OR-Toolsを用いると

• 様々な言語で数理最適化問題を記述可能
• 様甘な定式化方法に対応

②に数理最適化にGoogle OR-Toolsを用いると

• ソルバーを自由に選択可能
• 最新のアルゴリズムで高速に答えが求められる

シュレッダー復元のdemo
https://colab.research.google.com/gist/ohtaman/1ff72de0fc321fa36ccb2df0138deef9/shredder_mip.ipynb

定式化～再訪
→部分巡回路除去
　部分順回路：絵の左端と右端が繋がること

実行速度：50を超える紙片に対して現実的な時間で求解できない
紙片数 10：27.2msec
紙片数 20：5.0sec
紙片数 30：>1min
紙片数 50：???

ヒューリスティクスの利用
→ヒューリスティクス：発見的(手法)
　→必ずしも正しい答えを導ける訳ではない。正解に近い解を得ることができる。
　　→答えの制度が保証されない代わりに、解答に至るまでの時間が短い。

巡回セールスマン問題

課題との対応

• 目的関数：隣り合う紙片同士の非類似度の合計の最小化

　→総移動コスト

• 成約条件：各紙片は1列に並ぶ

　→セールスルートを1度ずつ巡る

• 決定変数：各紙片の並び順

　→巡回ルート

ルーティング問題を解く
→OR Toolsには巡回セールスマン問題などのルーティング問題に特化したヒューリスティクスが実装済み

• メリット：

　→混合整数計画法と比べ直感的に記述できる
　→問題の構造を利用して、大規模な問題を解ける

• デメリット：

　→近似解法なので最適解が得られるとは限らない
　→混合整数計画法と比べ変容性が低い
　→使い方にクセがある

ヒューリスティクスを用いたdemo
https://colab.research.google.com/gist/ohtaman/1ff72de0fc321fa36ccb2df0138deef9/shredder_routing.ipynb

改善

• 端の推定
• 非類似度の定義を変え、より最適解に近付ける
• 複数文書がシュレッダーされている状況への対応

---

更新日： 2020年10月31日 (土) 13時41分33秒