さまざまなバックグラウンドを持つ人々が Google のオペレーション リサーチチームに加わります。博士号を持ち、この分野でよく知られている人もいれば、数学の最適化を熱心に学ぶ優れたソフトウェア エンジニアもいます。
ソフトウェア エンジニアが OR エキスパートに「OR」について詳しく尋ねることがあります。Google は、以下から抜粋したドキュメントへの回答の収集を開始しました。これらは Google 社員個人の意見であり、Google の公式な推奨ではありません。ぜひチームとの会話をお楽しみください。
MOOC
| コース | 投稿者 | メモ | コメント |
|---|---|---|---|
| 離散最適化に関する Coursera クラス | Van Hentenryck | MIP と CP | Kvothe@: とても良かったです。ただし、最後の問題セットはまだ完成していません。 |
| 離散最適化のための基本モデリング | リー &スタッキー | CP を重視 | |
| 離散最適化のための高度なモデリング | リー &スタッキー | ||
| 離散最適化のためのアルゴリズム | リー &スタッキー | ||
| Picat で AI の問題をモデル化して解決する | バルトーク | ||
| OR(1): モデルとアプリケーション | カン | Zaphod@: これらと次の 2 つは、LP/IP に関するあらゆることをわかりやすく紹介する資料です。 | |
| OR(2): 最適化アルゴリズム | カン | ||
| OR(3): 理論 | カン |
LP と MIP の基本
| カバー | タイトル | 投稿者 | コメント |
|---|---|---|---|
 |
線形最適化の概要 | ベルツィマスとチチクリス | BlackLotus@: LP（および MIP 程度）には、この本が最適だと思います。 Patrick@: Bertsimas-Tsitsiklis は線形計画の「第 2 の学習コース」にふさわしいので、反対意見にすべきです。線形最適化の概要をご覧ください。 BadBoy@: これを見てみます。私はいつも、この人たちが物事を発表するのを好まないのですが、間違っているかもしれません。 Kvothe@: 第 10 章（「整数計画の定式化」）と第 11 章（「整数計画法」）は素晴らしい内容です。 |
 |
線形計画法 | ヴァンダーベイ | |
 |
組み合わせの最適化: 多面体と効率性 | シュライバー | SpiderWoman@: 昔の Schrijver の「組み合わせの最適化」が気に入っていたことは覚えていますが、非常に数学的なものであり、チームにおすすめする人にはおすすめしません。 |
 |
線形計画と整数計画の理論 | シュライバー | BadBoy@: ライブラリでインタビューをしたり、誰かに感心させたりするのもよいでしょう。純粋に 2 回精製された純粋な数学の博士号を取得していない限り、読むことはないでしょうし、好きになることもありません。ですから、LP や MIP から始める必要はありません。とはいえ、これには豊富な証拠と興味深い情報が含まれています。完全にユニモジュラーな行列やそれに伴うものです。また、参考文献は非常に詳細で、元の言語で引用されています。これはクヌースの「コンピュータ プログラミングの技術」の一種です。理解できないのはこちらだけです。 Kvothe@: 書いたことは読んでいませんが、書体だけでは不信感を抱きます。 |
 |
線形最適化の最初のコース | Lee | CC ライセンスの下で無料で利用できます。 |
 |
数学的最適化の概要 | フィシェッティ | BadBoy@: イタリア語版を見ましたが、とてもいいですね。Fischetti 全般の仕事が大好きです。 |
 |
線形計画法 | シュヴァタル | BadBoy@: 私はこの本は好きではありませんが、LP のすべてを学んだところで、表記も素晴らしいです。 |
 |
組み合わせの最適化 | パパディミトリウ &シュタイグリッツ | BadBoy@: とても良かったです。古くなっていますが、必ずお読みください。 Kvothe@: やや乾いた感じ。 |
 |
整数計画法 | Wolsey | Unicorn@: 非常に簡潔ですが、この分野の興味深い部分のほとんどを（ソルバーの観点から）カバーしています |
 |
整数計画法 | コンフォルティ、コルニュエホルス、ザンベリ | Patrick@: おそらく、MIP の理論と方法論に関する最新の書籍でしょう。 |
 |
組み合わせ最適化のファセット | Jünger & Reinelt | Patrick@: 理論的な話ですが、元 ZIB のディレクターである Martin Grötschel の 65 歳の誕生日を祝うときの発表内容に偏りがちですが、私はこの計算 MIP 調査の最新バージョンである「Tobias Achterberg and Roland Wunderling。Mixed Integer program: Analyzing 12 years of progress」。 |
 |
50 Years of Integer Programming: 1958-2008 | Jünger et al.、編集 | Patrick@: 少し古い内容ですが、歴史と MIP の最先端技術についてかなり読み取れます。 |
 |
ネットワーク・フロー・アルゴリズム | Williamson | Unicorn@: 直感的な操作で、ネットワーク フローに関する最近の結果が数多く記載されている優れた本です。ただし、ネットワーク フローに限り、一般的ではありません。フランス語でより完全なレビュー。 |
 |
考察するアルゴリズム: NP の難しい問題に対するアルゴリズム | ラフガーデン | Unicorn@: おそらく最も高度な書籍ではありません。それでも、一部の OR アルゴリズムの概要を説明します（アルゴリズム コースの観点から）。とても読みやすいです。フランス語でより完全なレビュー。 |
 |
実践的な最適化 | Gill、Murray、Wright | Unicorn@: 継続的な最適化に関する古いリファレンス ブックです。このアルゴリズム ファミリーについての説明が必要な場合は、こちらの書籍が参考になります。（フランス語でより完全なレビュー）。 |
 |
最適化とアダマール半微分微分積分の概要 | デルフォー | Unicorn@: 半差分最適化に関する専門的な書物です。簡単には入らない。フランス語でより完全なレビュー。 |
 |
Moment-SOS 階層: 確率、統計、計算幾何学、制御、非線形 PDE の講義 | ヘンリオン、コルダ、ラッサーレ | Unicorn@: 多項式を使った最適化を行っている方、または多項式を使って最適化したい方には、SoS 階層の基礎や馴染みのないアプリケーションについて学べます。フランス語でより完全なレビュー。 |
 |
オペレーション リサーチの概要 | ヒラーおよびリーバーマン | Kvothe@: 理論と実践をうまく組み合わせています。この分野を初めて学ぶ人にとって最適な最初のテキストです。ワークアウトの例と多くの演習が盛り込まれており、一部の回答は本の裏に記載されています。短所: この本はユーザーをウェブサイトに呼び込むのがやや難しく、時代遅れのソルバーを使用していることです。 |
調査レビュー
| まとめ | 投稿者 | コメント |
|---|---|---|
| 175 年にわたる線形プログラミング | チャンドゥルとラオ | BadBoy@: おすすめの記事のシリーズです。私は 1990 年代初頭に IBM でこの仕事に触れました。このような線形計画法を最初に発表したアイデアは誰に生まれたかわかりませんが、Vijay Chandru 氏と Jean-Louis Lassez 氏も関与しました。 この手法の素晴らしい点は、初級レベルの線形代数さえあれば理解できることです。LP では、ほぼすべての重要な定理を基本で証明できます。おすすめなのは、この LP の書籍、Chvatal とヴァンダーベイ語の何本かを記載し、実装に関する問題と関連書籍への参照を記載することです。Chvatal と Vanderbei には、確固とした数学的根拠が少し欠けています。 これは古いものであり、まもなく「200 年にわたる線形プログラミング」と改名されるべきです。これ以前に試行された可能性があります。 |
研究記事
| 記事 | 投稿者 | コメント |
|---|---|---|
| 線形計画のための新しい多項式時間アルゴリズム | カルマルカル | BadBoy@: Karmarkar のアルゴリズムに関する Karmarkar の論文。どのように記述すべきでないかの例。実装に何年もかかりましたが、その間に、これがさらに内部のポイント手法であることに気づきました。 |
モデリング
MIP
| カバー | タイトル | 投稿者 | コメント |
|---|---|---|---|
 |
数学的プログラミングでのモデル構築 | Williams | LP と MIP に重点を置いている。 Temere@: とても気に入らなかった。構造がおかしい（そして、人為的にページ数を増やしている）。それは「クラシック OR アプリケーション」（経済的なプランやおもちゃのような外観のプランニングに重点を置く）に大きく依存しており、Google で通常行っている MIP モデルとの関連性はほとんどありません。 Azalee@: 同調。 BadBoy@: この本は、当時はまだ素晴らしかったと思います。たぶん 2 年前に見たことがあるんだけど、情報が古い。また、著者とは 1990 年から知っていましたが、ISMP 2015 でも再び開催されました。引退した彼は素晴らしい人で、お金を支払って会議に出席し、今も優れたプレゼンテーションを行っています。特にフーリエ除去に関する論文は素晴らしいものでした。彼は LP とは何かという非常に幅広いビジョンを持っており、XpressMP の立ち上げに貢献しました。 |
 |
XpressMP による最適化の応用 | ゲレ、プリン、スヴォー、ヘイプケ |
ソルバー発行のモデリング ガイド
| ガイド | 説明 | コメント |
|---|---|---|
| MOSEK モデリング クックブック | 円錐凸最適化に重点を置いています。 | Unicorn@ 非線形モデリングを行う際の参考になります。 |
| MOSEK ポートフォリオ クックブック | ポートフォリオ最適化のための円錐モデル |
調査レビュー: MIP
| まとめ | 投稿者 | 説明 |
|---|---|---|
| 混合整数線形計画法の手法 | ビエルマ | 多面体のような区分的線形関数の結合のための帯分積公式の強さとサイズに焦点を当てます。理論的な話ですが、セクション 8 で段階的な製法などの実践的な手法をいくつか取り上げています。 |
| 非凸面区分線形関数: 高度な定式化とシンプルなモデリング ツール。 | Huchette & Vielma 氏 | 上記のレビューに含まれていない、区分的線形関数のより最近の手法。 |
調査レビュー: MINLP
| まとめ | 投稿者 | 説明 |
|---|---|---|
| 混合整数の凸表現の表現可能性 | Lubin、Vielma、Zadik | 凸緩和のみを目的としています。 |
不確実な状況下での最適化
確率的最適化
| カバー | タイトル | 投稿者 | コメント |
|---|---|---|---|
 |
講義: 確率的プログラミング: モデリングと理論 | シャピロ、デンチェヴァ、ルシュチンスキー | |
 |
確率的プログラミングの概要 | ビルジ・ルーヴォー | Unicorn@: トピックの理論的な概要です。確率的プログラミングの講義ほどおすすめしません。 |
調査レビュー
| まとめ | 投稿者 |
|---|---|
| 条件付きバリュー アット リスクの最適化 | ロカフェラー &ウリヤセフ |
堅牢な最適化
| カバー | タイトル | 投稿者 | コメント |
|---|---|---|---|
 |
堅牢な最適化 | ベンタル、エル ガウイ、ネミロフスキ | PDF。 Unicorn@: 以下のレビューに詳細が記載されていない場合に便利です。大部分は非線形の問題（通常はレビューには掲載されません）に重点を置いています。 係数の偏差が小さくても、実現可能性が大きくならないことが数値的に示されているセクション 1.1.2 がとても気に入っています。 |
 |
堅牢で適応性のある最適化 | Bertsimas & Dick Den Hertog 氏 | PDF。 Unicorn@: 堅牢な最適化に関する情報提供にぜひお役立てください。かなり詳細なデータで、アルゴリズムの面でももっとできることがあります。フランス語でより完全なレビュー。 |
調査レビュー
| まとめ | 投稿者 |
|---|---|
| 堅牢な最適化の実践ガイド | ゴリセン、ヤンコーグル、デン ヘルトーク |
| 堅牢な最適化の理論と応用 | ベルシマス、ブラウン、カラマニス |
研究記事
| 記事 | 投稿者 |
|---|---|
| Tracable Stochastic Analysis in High Dimensions via High Dimensions via Robust Optimization（PDF） | バンディ &ベルシマ |