Gerard P. Cornuejols

The 2011 John von Neumann Theory Prize is awarded by the Institute for Operations Research and the Management Sciences to Professor Gerard Cornuejols 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. In 1977, he (together with Marshall Fisher and George Nemhauser) won the Lanchester Prize for his work on facility location. He (together with Michele Conforti) showed that a matrix is balanced if and only if every one of its submatrices is perfect (equivalently, ideal) and he (together with Michele Conforti and M. R. Rao) provided a polynomial-time recognition algorithm for balanced matrices, a longstanding open problem. Their paper containing this result earned them the Fulkerson Prize for 2000 from the Mathematical Optimization Society. In 2009 he received the Dantzig award of the Mathematical Optimization Society for his cumulative contributions to optimization.

He (together with Egon Balas and Sebastian Ceria) developed the lift-and-project method for generating cutting planes for mixed 0-1 programs. In addition, he (together with Kent Andersen and Yanjun Li) showed how the classical mixed-integer Gomory cuts can be embedded in a branch and bound framework that renders them efficient. These developments have led to the incorporation of such cuts into the branch- and- bound codes of the leading commercial solvers and have played a major role in the state of the art in integer programming during the past two decades.

In the early 2000s he (together with several of his former students) made decisive progress in proving the strong perfect graph conjecture, open for the past 40 years. It says that a graph is perfect if and only if it contains no odd hole or anti-hole (complement of a hole) as an induced subgraph. Their work has helped the team (Chudnovski, Seymour, Robertson and Thomas) who finally proved the conjecture in a 150 page paper.