Gérard Cornuéjols, IBM University Professor of Operations Research at Carnegie Mellon University’s Tepper School of Business, has been awarded the prestigious George B. Dantzig Prize. This honor, which is bestowed only once every three years, is awarded jointly by the Mathematical Programming Society and the Society for Industrial and Applied Mathematics, in honor of George Dantzig, the “father” of linear programming and a pioneer in the field of Operations Research.
The 2009 Dantzig prize recognizes Professor Cornuéjols for his deep and wide-ranging contributions to mathematical programming, including his work on balanced and ideal matrices and perfect graphs, and his leading role in the work on general cutting planes for mixed integer programming over many years covering both theory and computation.
“Gérard 's best known contributions are to the theory of perfect graphs,” says Egon Balas, University Professor of Industrial Administration and Applied Mathematics, The Thomas Lord Professor of Operations Research. “This concept is important because several basic problems that are very hard to solve for a general graph become easily solvable if the graph is perfect. However, given an arbitrary graph, it is hard to tell whether it is perfect or not."
Half a century ago the French mathematician Claude Berge conjectured that a graph is perfect if and only if it has no odd-length cycles or complements of cycles. In 2002, a group of mathematicians at Princeton proved this conjecture—the Strong Perfect Graph Theorem—partly by using results established a couple of years earlier by Gérard. In 2005, Gérard, along with two of his former students, and two members of the above mentioned Princeton group, issued a joint paper defining an efficient procedure for recognizing when a graph is perfect. These results represent an important breakthrough in algorithmic graph theory.
Gérard Cornuéjols is currently working in the area of cutting planes. “One of the really exciting developments in this field is that software for optimization has improved tremendously. Now we can solve real world, practical problems that were impossible 10 or 20 years ago. I am exploring some ideas to make optimization software even more efficient,” said Cornuéjols.
Professor Cornuéjols, has been a faculty member at the Tepper School for thirty years. He completed his undergraduate work in civil engineering in Paris, France, where he enjoyed learning about issues related to network flows. He earned his Ph.D. from Cornell University and came to Carnegie Mellon University shortly thereafter.
“CMU is unique among American universities in that its Ph.D. program in Operations Research is housed in the business school,” adds Cornuéjols. “For me, the environment at the Tepper School has been a source of freedom rather than a constraint on my research. Teaching MBA students keeps reminding my colleagues and I of the need for user-friendly, reliable optimization tools. And there is still much work left to do for us researchers in the mathematical programming community.”