Past Awards
The 2015 Lanchester Prize is awarded to Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli for their book Integer Programming, Springer, Switzerland, 2014.
Advances in the theory of integer programming have gone hand in hand with advances in solving integer programs in practice. This textbook presents the fundamentals of the area, highlighting the mathematical elegance of the foundations of the field, as well as bringing the reader to the edge of the research frontier. The writing blends clarity of exposition with a dedication to infusing the reader with the needed geometric intuition. Several well-known results especially benefit from this fresh presentation, including the theory of split inequalities and the explicit description of the convex hull of a finite union of polyhedra. Even the most recent theoretical gems are included, such as the exponential lower bound on the size of extended formulations of the matching polytope as well as the power of hierarchies of relaxations based on semidefinite programming. This advanced theory is complemented by a thorough development of the algorithmic and modeling aspects of the area, making this a truly complete survey of integer programming, which will serve the next generation of researchers to further advance the field in the years ahead.
The committee members (David Shmoys, chair, Michael Ferris, Ramesh Johari, Chung Piaw Teo, Bert Zwart) are pleased to designate Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli as recipients of the 2015 Lanchester Prize.
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.