While Google is, of course, heavily active in analytics, the company has not been known for its operations research. The “ethos” of the company has been heavily computer science based. So, while I would count much of what they do as “operations research”, they probably would not use that label.
The line between operations research and computer science is not easy to draw, but linear programming falls pretty strongly on the operations research side: it is the sort of “heavy machinery” that occurs often in OR. Given the variety of problems a company like Google faces, it is not surprising that they would end up with some problems for which linear programming is the right approach. Or not. In a recent discussion, Vijay Gill, senior manager of engineering and architecture was somewhat cagey on how computer load redistribution was being done:
Gill even seems to be saying that the company hopes to instantly redistribute workloads between data centers.
“How do you manage the system and optimize it on a global-level? That is the interesting part,” Gill continued. “What we’ve got here [with Google] is massive – like hundreds of thousands of variable linear programming problems that need to run in quasi-real-time. When the temperature starts to excurse in a data center, you don’t have the luxury to sitting around for a half an hour…You have on the order of seconds.”
Heiliger asked Gill if this was a technology Google is using today. “I could not possibly comment on that,” Gill replied, drawing more laughter from his audience.
In possibly unrelated, but possibly related, news, the Google Open Source Blog has an announcement of an open-source simplex code:
SimplexSolver is an easy-to-use, object-oriented method of solving linear programming problems. We’re happy to announce today that we’ve Open Sourced the code that runs the newly released Google Spreadsheets Solve Feature and made it a part of Apache Commons Math 2.0.
Thanks to my former office mate in Auckland Hamish Waterer and to Andrew Mason for passing along these pointers.
When I was at ILOG, I knew two people who were doing mathematical programming at Google, and I know a couple of people who do constraint programming have joined them. So I can confirm that they have some expertise in OR. That said, Google can be very secretive about their work, so I have little idea about what they were doing.
I also find it very strange that Google created their own simplex solver. There are already multiple open source implementations of LP and MIP. Why didn’t they simply use one of these? If they had so much free time, they could have enhanced these existing open source projects. Sounds like a suboptimal use of Google’s time.
Does the solving program being integrated into google spreadsheets imply the google documents are about to get a lot more fully featured?
Greg, they explain in the announcement that “[w]hile numerous other libraries are available that run linear optimization problems, SimplexSolver is the first written in Java with a commercially-friendly license.” Presumably the other open-source solvers either aren’t Java, or aren’t using a “commercially-friendly” license.
some more comments on this development at
http://dualnoise.blogspot.com/2009/07/gooplex-go-google-wake-up-coin-or.html
I took a quick look at the source. It’s a dense solver, using tableaus.