INFORMS News: Cornuejols earns von Neumann Theory Prize

INFORMS President Rina Schneur, von Neumann Theory Prize recipient Gerard Cornuejols and Committee Chair Jim Dai (l-r).

INFORMS President Rina Schneur, von Neumann Theory Prize recipient Gerard Cornuejols and Committee Chair Jim Dai (l-r).

Gerard Cornuejols, a professor at Carnegie Mellon University, won the 2011 John von Neumann Theory Prize from INFORMS 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” Prize committee chair Jim Dai made the presentation at the INFOMS Annual Meeting in Charlotte, N.C.

The prize recognizes scholars who have made fundamental, sustained contributions to theory in operations research and the management sciences.
The award citation read in part:

In 1977, [Cornuejols] (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 [Cornuejols] received the Dantzig award of the Mathematical Optimization Society for his cumulative contributions to optimization.

[Cornuejols] (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, [Cornuejols] (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.