Google seems to be getting the idea that operations research has a lot to add to the company. This is a long way from the time where I got the following response from a google software engineer at an information systems conference: “Integer programming? I tried it: it doesn’t work”. Oh, really?

This change is great for our field: the line between operations research and computer science is extremely fuzzy and is getting fuzzier as “business analytics” unites traditionally CS areas such as data mining with traditionally OR areas such as optimization. Operations Research needs to be seen as a key reason for the continuing success for companies like Google.

If you are in Europe, you can even get some money for a post-doc or other research expense from google, as per this announcement from Laurent Perron:

Object: Call for Proposal for Google Focused Grant Program on Mathematical Optimization and Combinatorial Optimization in Europe.

Deadline: November 25th (strict).

Contact: proposal should be sent to both Laurent Perron (lperron@google.com) and Michel Benard (benard@google.com).

Format: A proposal is a 3 pages document following the format described in http://research.google.com/university/relations/research_ awards.html The purpose of this program is to facilitate more interaction between Google and academia and also nurture stronger relations and partnerships with universities. The intent of this focused awards program is to support academic research aimed at improving the theory and applications of mathematical and combinatorial optimization (Operations Research, Constraint Programming, Meta-Heuristics). Google funds Research Awards unrestricted and retains no intellectual property from the research. We prefer if the results from the research are open sourced and widely published. Awards through this program are for one year in the range of $10K-$150K.

A typical grant will cover 1 Post-Doctoral student for 1 year. This program is restricted to Europe.Areas that are of particular interest include (but are not limited to):

* Inference and relaxation methods: constraint propagation, cutting planes, global constraints, graph algorithms, dynamic programming, Lagrangean and convex relaxations, counting based inferences and heuristics, constraint relaxation based heuristics.

* Search methods: branch and bound, intelligent backtracking, incomplete search, randomized search, column generation and other decomposition methods, local search, meta-heuristics, large scale parallelism.

* Integration methods: static/dynamic problem decomposition, solver communication, transformations between models and solvers, collaboration between concurrent methods, models, and solvers.

* Modeling methods: comparison of models, symmetry breaking, uncertainty, dominance relationships, model compilation into different technologies (CP, LP, etc.), learning (CP, LP) models from examples.

* Innovative applications derived from OR techniques.

As a point of comparison, last year, we funded 9 grants in the following fields: Explanations in Constraint Programming, SAT techniques in Scheduling, Just-In-Time scheduling, Complex Bin-Packing, Parallel Resources in Scheduling, Convex Integer Programming, Ride sharing, Large Scale Mixed Integer Programming, and Territory Design.

Google values well written proposals that fit into the 3 page format + references. These proposals should include the following sections:

– A clear description of the problem the authors are trying to solve, and the potential impact they could have if the research is successful.

– An overview of the state of the art in this field and an explanation of why the proposed research is innovative.

– A precise understanding on how the authors are going to solve this problem.

– A convincing experimental method that will prove the authors are solving the real problem on realistic data instances, and that will measure the actual gains.

– The biography and a link to recent publications from the P.I. related to the proposal.Finally, receiving a Google Research Award does not grant access to Google data. In some instances Google researchers may however be interested in collaborating on the problem formulation and the algorithmic solution.