Python

「そうだ、数理最適化、やろう。」ってなった時にめっちゃ参考になったリンク集&参考書

最近弊社でにわかに最適化が盛り上がっている空気を感じます。

最適化というのは我々データ分析官からすると、太宰治のようなもので、突如としてその世界に引き込まれどっぷり浸かってしまう時があるものです。
僕も例に漏れず、突如として胸が苦しくなるほど数理最適化をしたくなる時がありました。
いつだったでしょうか、2年くらい前のそうちょうど今日みたいに星が降る夜でした

どうでもいい前置きはいいとして、その時に諸々調べて参考にしたWebページを共有させていただきます。
2年前(2018年くらい)なので、若干古いものもあるかもしれませんが、改めてざっと調べ直してみた感じですとそこまでのブレイクスルーはないような感じでした。が、多少アップデートしております。

一点注意として、当時の僕の興味は完全に、ナップサック問題や工場ー倉庫ー小売の輸送最適化、スケジューリング問題といった、(混合)整数計画問題にありましたので、紹介する記事にもその辺のバイアスが生じていることが想定されます。あらかじめご承知を。

 

 

◆【総論】とりあえずこれを見て概観を掴む

 

これめっちゃわかりやすいな〜って感じで、改めて読み返しつつレビューしてたら長くなりすぎちゃったので、別記事にまとめました。

数理最適化案件とAI/機械学習案件とのアナロジー 「やってみなければわからない」中で僕たちDSはどうするか本記事では表題に関して、脳筋系ゆるふわVTuberこと入社2年目DSの岡部がお送りいたします。(DS=データサイエンティスト) 発...

 

◆【理論・実践】(2021年時点で)オススメの参考書

最大のアップデートはこちらの2冊です。参考書は時代の流れに合わせていいものが出てくるものですね。もちろん過去の参考書にもいいものはたくさんありますが、日進月歩の分野である以上、新しいものに軍配が上がりやすい構図はあると思います。

  • しっかり学ぶ数理最適化 モデルからアルゴリズムまで
  • Pythonではじめる数理最適化: ケーススタディでモデリングのスキルを身につけよう

以下それぞれの所感です

 

【理論】「最適化分野全般を知るための『最適解』」とも言われている教科書

僕が最適化にハマっていた当時は様々な本をパラパラ眺めつつ、それらを統合して全体像を掴む感じだったのですが、この本は一冊だけで分野全体を概観できる現状最強の入門書だと思います。見た目も綺麗で説明も分かりやすい。
ただし、ここで入門と言っているのは、あくまで「研究分野としての入門」のことを指しているので、僕の所感としては例えばM1のゼミでやって半年〜一年って感じの骨太な一冊です。実務で使う場合はとりあえず関連するところから読む感じの使い方がいいでしょう。

理論を学ぶ点においては文句のつけようがない一方、実際コードを動かすハンズオンは皆無な点には注意が必要です。
これはまあ当然と言えば当然で、理論に振り切っているからこそ、ここまでの幅と深さを両立できているわけですから。

 

【実践】実務家によって書かれた最適化を実践的に「使う」ための教科書

「しっかり〜」が理論を抑える一冊とするなら、こちらはケーススタディで実際に手を動かして使い所を理解する一冊。完全に相補的です。

「しっかり〜」と対をなして、現時点における数理最適化入門書の決定版だと思います。実務家が書いているだけあってそれぞのケースが本当に生々しい。「遠足に持っていくお菓子の最適化」とはもう卒業しましょう。これもう自分の体験談なのでは?というくらい実践的な内容で数理最適化の使い方を学ぶことができます。

さらにAPIとWebアプリケーションの開発なる章まであり、チューンアップをすればこのまま自社のアプリに載せられそう、そんな空気感すらあります。

ただしPython限定です、素直にPython使いましょう(信者並の感想)。

 

◆【理論・実践】オペレーションズ・リサーチ学会の機関誌

公益社団法人 日本オペレーションズ・リサーチ学会の機関誌です。アーカイブもめちゃくちゃ見れて非常に参考になります。ただ、もしかしたら期間限定一般公開かもしれないので、将来的にはリンク切れになる可能性があります。

アーカイブ

(2006年以前):機関誌 経営の科学 オペレーションズ・リサーチ
(2006年以降):機関誌「オペレーションズ・リサーチ」 Communications of the Operations Research Society of Japan

 

個人的には特に以下の記事が参考になりました。

 

◆【理論・実践】個人的に超参考になったキーパーソンのWebサイト

久保’s ホームページ

2021年12月現在、東京海洋大学教授である久保幹雄先生のホームページ。非常に発信力のある方で、noteからYoutube、Pythonで解く最適化100本ノックまでコンテンツもりもりです。データサイエンス練習帳もあるよ。
例えば最適化で言うと、「100の最適化問題(Python言語による実務で使える100+の最適化問題)」とあるページをみるといいでしょう。
Pythonでコーディングすることで実際に手を動かしつつ理論的な側面も同時に学ぶことができます。
このレベルの質と分量が無料で見れるのはハッキリ言って異常です

本ページに書いてある以下の「格言」は個人的に最適化に取り組む際の金言として心に刻みつけております

格言

  • 多項式時間の厳密解法にこだわるなかれ.言い換えればwell-solved special caseは役に立たない.
  • 最悪値解析にこだわるなかれ.最悪の場合のインスタンスというのは滅多に実務には現れない.そのようなインスタンスに対して,最適値の数倍という保証をもつ近似解法というのは,通常のインスタンスに対して良い解を算出するという訳ではない.我々の経験では,ほとんどの場合に役に立たない.
  • 確率的解析にこだわるなかれ.
  • ベンチマーク問題に対する結果だけを信じるなかれ.
  • 精度にこだわるなかれ.計算機内では,通常は,数値演算は有限の桁で行われていることを忘れてはいけない.
  • 手持ちの解法にこだわるのではなく,問題にあった解法を探せ.

 

 

宮代隆平のwebページ

2021年12月現在、東京農工大学の准教授である宮代隆平先生のホームページ。
整数計画法メモ」のページが特に参考になります。特に「よくある質問」として過去のトラブルシューティングログのようなQAが大量にまとまってますので、実装時につまづいた時はこちらを参考にすればいいかと。

 

◆【実践】細けぇこたぁいいからPythonで実装したい

最適化におけるPython

この記事自体でPython数理最適化事始めができる上に、めちゃくちゃ参考ページが紹介されてます。あとは自分が解きたい問題に合わせて、同じような問題を解いてる参考ページを探したり、上で紹介したオペレーションズ・リサーチ学会の記事を読みつつ自分で定式化してみたりするといいでしょう。

 

◆【実践】有償ソフトウェアGurobiのホームページにある問題をPuLPで解く

Functional Code Examples

有償のものとしては非常に知名度の高い最適化ソフトウェアGurobi Optimizer。そのホームページには最適化問題のコードサンプルがいくつか掲載されています。
僕は練習問題としてここにあるサンプルをPuLPで解けるように実装したりしてました。

 

 

◆【実践】「久保先生、、、最適化がしたいです」ってなった時に見るサイト

実際の最適化問題を瞬時に解くためのトレーニング

上でも紹介した久保幹雄先生のnote記事。以下の文言から始まり、最適化を解く上でのコツとか心構えのようなものをレクチャーしてくれてます。

最近,実際の最適化問題に挑戦する若手(?)の研究者が増えてきたようだ.嬉しいことだが,普段からトレーニングしていないので,結構時間がかかってしまったり,モデル化がうまくいかなかったりしてトラブルことも,ままあるようだ.

モデル化の部分はアートであるが,トレーニングはできるので,その方法を書いておこう.

以下のサイトを参考にせよとのこと(note内で紹介されている2サイトのうち片方は現在リンク切れ)

 

Taizo
脳筋系データサイエンティスト。筋肉は裏切らない。筋肉。