{"id":1482,"date":"2011-06-24T11:48:56","date_gmt":"2011-06-24T15:48:56","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1482"},"modified":"2011-06-24T11:48:56","modified_gmt":"2011-06-24T15:48:56","slug":"another-operations-research-challenge-roadef-euro-and-google","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2011\/06\/24\/another-operations-research-challenge-roadef-euro-and-google\/","title":{"rendered":"Another Operations Research Challenge: ROADEF, EURO, and Google"},"content":{"rendered":"

I am a big fan of “challenges” in operations research<\/a>.\u00a0 Almost twenty years ago, I ran a DIMACS Challenge on finding cliques, coloring graphs and solving satisfiability problems.\u00a0 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.\u00a0 I also\u00a0 met a large number of people and took pride in creating something useful to many.<\/p>\n

ROADEF (the French OR Society) has run a series of Challenges over the years.\u00a0 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<\/a>).\u00a0 The recently announced 2012 Challenge<\/a> is no different.\u00a0 The problem to be solved comes from Google, and involves assigning jobs to machines.<\/p>\n

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
\ncapacity 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.<\/p><\/blockquote>\n

The problem description then goes on for 10 pages, including issues such as locations, services, conflicts, moving costs and much, much more.\u00a0 This certainly looks like a real problem and one that a firm like Google would need to solve routinely and quickly.\u00a0 I can also see a number of different approaches that might work.\u00a0 I look forward to seeing what methods are successful for this.<\/p>\n

This Challenge is sponsored by ROADEF<\/a>, EURO<\/a>, and Google<\/a>.\u00a0 Google, for all its success, has only recently started to use and support operations research<\/a> (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.\u00a0 Now, how about some million dollar prizes to go with it … (though 20,000 euros is not to be sniffed at).<\/p>\n","protected":false},"excerpt":{"rendered":"

I am a big fan of “challenges” in operations research.\u00a0 Almost twenty years ago, I ran a DIMACS Challenge on finding cliques, coloring graphs and solving satisfiability problems.\u00a0 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.\u00a0 I also\u00a0 … Continue reading “Another Operations Research Challenge: ROADEF, EURO, and Google”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,11],"tags":[],"class_list":["post-1482","post","type-post","status-publish","format-standard","hentry","category-challenges","category-companies"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1482","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1482"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1482\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1482"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}