I am a big fan of “challenges” in operations research. Almost twenty years ago, I ran a DIMACS Challenge on finding cliques, coloring graphs and solving satisfiability problems. That challenge gave a clear picture of where we were then in those areas and showed the variety of approaches possible for those three problems. I also met a large number of people and took pride in creating something useful to many.
ROADEF (the French OR Society) has run a series of Challenges over the years. These challenges have been inspired by real-world problems and are generally very rich in detail (details on past Challenges, including test instances, are available at the Challenge site). The recently announced 2012 Challenge is no different. The problem to be solved comes from Google, and involves assigning jobs to machines.
The aim of this challenge is to improve the usage of a set of machines. A machine has several resources as for example RAM and CPU, and runs processes which consume these resources. Initially each process is assigned to a machine. In order to improve machine usage, processes can be moved from one machine to another. Possible moves are limited by hard constraints, as for example resource
capacity constraints, and have a cost. A solution to this problem is a new process-machine assignment which satisfies all hard constraints and minimizes a given objective cost.
The problem description then goes on for 10 pages, including issues such as locations, services, conflicts, moving costs and much, much more. This certainly looks like a real problem and one that a firm like Google would need to solve routinely and quickly. I can also see a number of different approaches that might work. I look forward to seeing what methods are successful for this.
This Challenge is sponsored by ROADEF, EURO, and Google. Google, for all its success, has only recently started to use and support operations research (though the line between computer science and operations research is very fuzzy in this area), so I am delighted to see their support of this Challenge. Now, how about some million dollar prizes to go with it … (though 20,000 euros is not to be sniffed at).