Carnegie Mellon University

Gérard P. Cornuéjols

IBM University Professor of Operations Research, Emeritus

Tepper School of Business
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213

P: 412-268-2284


Gerard Cornuejols


Ph.D., Cornell University


My current research is in combinatorial optimization and graph theory, with emphasis on the algorithmic aspects. My current focus is on the study of perfect graphs, balanced matrices and the max-flow min-cut property. Another line of my research deals with NP-hard combinatorial optimization problems through the study of relaxations. Using polyhedral combinatorics, contributions are made to the theory of the set covering, location, vehicle routing, and traveling salesman problems.

Select Publications

Elementary Closures for Integer Programs (with Y. Li), Operations Research Letters 28 (2001) 1–8.

The Packing Property (with B. Guenin and F. Margot), Mathematical Programming A 89 (2000) 113–126.

Decomposition of Balanced Matrices (with M. Conforti and M.R. Rao), Journal of Combinatorial Theory B 77 (1999) 292–406.

A Class of Hard Small 0-1 Programs (with M. Dawande), INFORMS Journal on Computing 11 (1999) 205–210.

Finding an Even Hole in a Graph (with M. Conforti, A. Kapoor and K. Vuskovic), Proceedings of FOCS (1997) 480–485.

Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework (with E. Balas and S. Ceria), Management Science 42 (1996) 1229–1246.

Perfect Matchings in Balanced Hypergraphs (with M. Conforti, A. Kapoor and K. Vuskovic), Combinatorica 16 (1996) 325–329.

A Class of Logic Problems Solvable by Linear Programming (with M. Conforti), Journal of the ACM 42 (1995) 1107–1113.

Conforti, M., Cornuejols, G. and Truemper, K. (1994), "From Totally Unimodular to Blanced 0, +1 Matrices: A Family of Integer Polytopes," Mathematics of Operations Research 19: 21–23.

Cornuejols, G. and Novick, B. (1994), "Ideal 0,1 Matrices," Journal of Combinatorial Theory B 60: 145–157.

Balas, E., Ceria, S. and Cornuejols, G. (1993), "A Lift-and-project Cutting Plane Algorithm for Mixed 0-1 Programs," Mathematical Programming 58: 245–324.

Conforti, M. and Cornuejols, G. (1990), "A Decomposition Theorem for Balanced Matrices," Integer Programming and Combinatorial Optimization, R. Kannan and W.R. Pulleyblank eds., Waterloo University Press, 147–169.

Brezovec, C., Cornuejols, G. and Glover, F. (1988), "A Matroid Algorithm and its Application to the Efficient Solution of Two Optimization Problems on Graphs," Mathematical Programming 42: 471–487.

Cornuejols, G.P. (1988), "General Factors of Graphs," Journal of Combinatorial Theory B 45: 185–198.

Google Scholar Citation List