People with different backgrounds join Google's Operations Research team. Some are PhDs and well-known in their field; others are excellent software engineers enthusiastic about learning mathematical optimization.
Sometimes the software engineers ask the OR experts how to learn more about OR. We started to collect our answers in a document, excerpted below. These are opinions of individual Googlers, not official Google endorsements. We hope you enjoy eavesdropping on our team conversation!
|Coursera class on Discrete Optimization||van Hentenryck||MIP & CP||Kvothe@: I loved this. Still haven't finished the final problem set though.|
|Basic Modeling for Discrete Optimization||Lee & Stuckey||More of a focus on CP|
|Advanced Modeling for Discrete Optimization||Lee & Stuckey|
|Solving Algorithms for Discrete Optimization||Lee & Stuckey|
|Modeling and Solving AI Problems in Picat||Barták|
|OR(1): Models and Applications||Kung||Zaphod@: These and the next two are a great introduction to all things LP/IP.|
|OR(2): Optimization Algorithms||Kung|
LP & MIP Basics
|Introduction to Linear Optimization||Bertsimas & Tsitsiklis||BlackLotus@: For LP (and to a lesser extent MIP), I think this book is best.
Patrick@: Downvoting Bertsimas-Tsitsiklis as it's more for a "Second Course" on linear programming, and for that it's probably best together with Introduction to Linear Optimization.
BadBoy@: I need to have a look at this one. I usually do not like the way these guys present stuff, but I may be wrong.
Kvothe@: Chapters 10 ("Integer programming formulations") and 11 ("Integer programming methods") are great.
|Combinatorial Optimization: Polyhedra and Efficiency||Schrijver||SpiderWoman@: I remember liking Schrijver's "Combinatorial Optimization" way back when, but it's very mathematical and not something I'd recommend to someone joining the team for example…|
|Theory of Linear and Integer Programming||Schrijver||BadBoy@: Cool to show off in your library, when doing an interview or to impress someone. You most likely will not read it, and you won’t like it, unless you have a PhD in pure, twice-distilled math. So not the thing to start LP or MIP with. This being said, it contains a wealth of proofs and interesting information. Things like totally unimodular matrices and what they entail. And the bibliography is incredibly well detailed, with citations in the original languages. It’s a kind of Knuth’s Art of Computer Programming. Only this one is not digestible.
Kvothe@: Haven't read it, but distrust it based on typeface alone.
|A First Course in Linear Optimization||Lee||Freely Available under a CC license!|
|Introduction to Mathematical Optimization||Fischetti||BadBoy@: I went through the Italian version. Looks very good. I love what Fischetti does in general.|
|Linear Programming||Chvatal||BadBoy@: I don't like the book but it's where I learnt everything LP, and the notation is great.|
|Combinatorial Optimization||Papadimitriou & Steiglitz||BadBoy@: I loved it. It’s outdated, but you should read it.
Kvothe@: A bit dry for my taste.
|Integer Programming||Wolsey||Unicorn@: Very terse, but covers most of the interesting parts of the field (from a solver perspective)|
|Integer Programming||Conforti, Cornuéjols, & Zambelli||Patrick@: Probably the most up-to-date book on MIP theory/methodology.|
|Facets of Combinatorial Optimization||Jünger & Reinelt||Patrick@: More on the theoretical side and biased towards the work by former ZIB director Martin Grötschel (it's from his 65th birthday celebration), but it includes what I think is the latest version of this computational MIP survey: "Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress".|
|50 Years of Integer Programming: 1958-2008||Jünger et al., ed.||Patrick@: Slightly outdated, but a very good review of history and MIP state-of-the-art.|
|Network Flow Algorithms||Williamson||Unicorn@: A good book with many very recent results about network flows, while still being intuitive. Only for network flows, though, so not that generic. More complete review in French.|
|Algorithms Illuminated: Algorithms for NP-Hard Problems||Roughgarden||Unicorn@: Probably not the most advanced book of the pack! Still, it provides an intro to some OR algorithms (from the point of view of an algorithms course). Very readable! More complete review in French.|
|Practical Optimization||Gill, Murray, & Wright||Unicorn@: Old reference book about continuous optimization. If you need any explanation about this family of algorithms, this book has you covered. (More complete review in French.)|
|Introduction to Optimization and Hadamard Semidifferential Calculus||Delfour||Unicorn@: Very formal book about semidifferential optimization. Not easy to get into. More complete review in French.|
|The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs||Henrion, Korda, & Lasserre||Unicorn@: If you’re optimizing with polynomials or wondering how far you can go with these, you will get the basics of the SoS hierarchy and unfamiliar applications. More complete review in French.|
|Introduction to Operations Research||Hillier & Lieberman||Kvothe@: A nice mix of theory & practice. A good first text for people new to the field, with worked-out examples and lots of exercises, some with answers in the back of the book. Downsides: the book tries a bit too hard to funnel users to its website, and it uses obsolete solvers.|
|175 Years of Linear Programming||Chandru & Rao||BadBoy@: It's a great series of articles. I was exposed to this at IBM in the early 1990s. I do not know who first had the idea of presenting linear programming like this, but Vijay Chandru and Jean-Louis Lassez were involved, too.
The nice thing about it is that you need only entry-level linear algebra to understand it, and you can prove almost any important theorem in LP with the basics. The best would be a book on LP with this, plus some Chvatal, some Vanderbei, and then implementation issues and references to the relevant books. Chvatal and Vanderbei lack a bit of solid mathematical ground.
It's old, and should soon be renamed 200 years of Linear Programming. It's possible there were earlier attempts.
|A new polynomial-time algorithm for linear programming||Karmarkar||BadBoy@: Karmarkar’s paper on Karmarkar’s algorithm. The example of how a paper should not be written. It took years to get to a working implementation, and in the meantime they discovered it was yet another interior point method.|
Solver-issued Modeling Guides
|MOSEK Modeling Cookbook||Focuses on conic convex optimization.||Unicorn@ A real reference for me when doing nonlinear modelling.|
|MOSEK Portfolio Cookbook||Conic models for portfolio optimization|
Research Reviews: MIP
|Mixed integer linear programming formulation techniques||Vielma||Focuses on the strength and size of mixed-integer formulations for unions of polyhedra-like piecewise linear functions. More on the theoretical side, but includes some practical techniques like incremental formulations in section 8.|
|Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools.||Huchette & Vielma||More recent techniques for piecewise linear functions that are not included in the above review.|
Research Reviews: MINLP
|Mixed-integer convex representability||Lubin, Vielma, & Zadik||For convex relaxations only.|
Optimization Under Uncertainty
|Optimization of Conditional Value-at-Risk||Rockafellar & Uryasev|
|Robust Optimization||Ben-Tal, El Ghaoui, & Nemirovski||PDF.
Unicorn@: A great reference if the reviews below aren't detailed enough. A large part is devoted to nonlinear problems (typically not presented in the reviews).
I really like its Section 1.1.2, because it shows numerically that small coefficient deviations can make large infeasibilities.
|Robust and Adaptive Optimization||Bertsimas & Dick Den Hertog||PDF.
Unicorn@: Excellent reference on anything regarding robust optimisation! It’s quite thorough, it could do with a bit more on the side of algorithms. More complete review in French.
|A Practical Guide to Robust Optimization||Gorissen, Yanıkoğlu, & den Hertog|
|Theory and Applications of Robust Optimization||Bertsimas, Brown, & Caramanis|
|Tractable Stochastic Analysis in High Dimensions via Robust Optimization (PDF)||Bandi & Bertsimas|