When Gérard Cornuéjols was still a Ph.D. student, a professor presented him with an open problem that was first proposed in 1960. Little did he know that it would fuel his curiosity – and much of his research -- for the next two decades.
Known as the Strong Perfect Graph Conjecture, it was a problem on which Cornuéjols worked through the 1980s and 1990s. In many ways, it was also the launch point for other parts of his career, because perfect graphs led to a related interest in integer programming, an area in which he has worked for nearly 20 years.
For his work on these and other projects, Cornuéjols, the IBM University Professor of Operations Research, has been honored with the INFORMS John von Neumann Theory Prize in 2011. The award is widely regarded as the most prestigious honor in operations research. Past faculty winners include Herbert Simon (1988) and Egon Balas (1995). The ceremony was held in mid-November at the INFORMS annual meeting in Charlotte, N.C.
“I was not anticipating this at all. Those are really very prestigious prizes, and there are a number of very excellent researchers in optimization, so I was surprised they gave it to me,” says Cornuéjols. “I’m very honored.”
The prize recognized Cornuéjols for his fundamental and broad contributions to discrete optimization, including his deep research on balanced and ideal matrices, perfect graphs and cutting planes for mixed integer optimization.
“Gérard’s work in discrete optimization has fundamentally changed the way we solve problems in practice, through his work on cutting plans, and has given us deep insights into the theoretical structure of discrete optimization problems,” says Michael Trick, senior associate dean, education and himself a professor of operations research. “Through his work, we much better understand when optimization problems are easy and when they are hard.”
His early work addressed facility location problems. For example, from a practical standpoint, this research might help a business find the optimal location for a warehouse to serve retail outlets or clients while minimizing overall costs.
Then, of course, there was the Strong Perfect Graph Conjecture, which was finally solved by another team in 2002, thanks in part to an approach developed by Cornuéjols’ team.
“We realized how difficult it was, and we realized how much work we had to do,” he says, adding that the other team’s solution included 150 pages of hard proofs. “It really was a monumental result … We felt vindicated that we were really on the right path, it’s just that the path was very long.”
The answer that he and so many others sought is summarized in a single sentence: A graph is perfect if and only if it is a Berge graph. But the simplicity of that statement belies the decades of work that were invested by those who pursued the answer.
“In some sense, I was relieved, because the solution was so complicated,” says Cornuéjols, although he admits that he did think: “Now what?”
Because he found himself on a campus that offered such a challenging environment, he has never been short of answers to that question. Cornuéjols arrived in 1978, and laughs when he recalls how he thought it would be just a temporary position, because he was considering a return to his native France.
“In some sense, I really only changed my mind very recently,” he adds.
Ultimately, it was the opportunity to work with gifted colleagues, deans and students that kept him in Pittsburgh.
“I have a pretty clear agenda of what I want to work on,” he says. “It’s really wonderful to be able to do research with such talented students.”
He also believes the future of operations research is a bright one.
“There is still a lot to do in this field, and it’s surprising how, at every conference, [so] many fantastic results are presented. It’s a very active, very dynamic field.”
Back to Tepper School homepage