Awarded Dantzig Prize

Cornuejols Pioneers New Solutions

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. The prize, which is bestowed only once every three years, is awarded jointly by the Mathematical Programming Society and the Society for Industrial and Applied Mathematics.

The researcher's role in revolutionizing mathematical programming is prominent — and has many real-world applications. For example, graph theory — a field in which Cornuéjols has pioneered new solutions — is used for everything from understanding relationships in social networks to analyzing the threat of extinction to a particular species.

The 2009 Dantzig prize recognizes 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," said 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 Cornuéjols.

In 2005, Cornuéjols, 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.

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," he said.

Cornuéjols, has been a faculty member at the Tepper School for 30 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.

"Carnegie Mellon is unique among American universities in that its Ph.D. program in Operations Research is housed in the business school," he added.

"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."

Homepage Story Archives