Gerard Cornuejols

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

Posner Hall Room 232A
gc0v@andrew.cmu.edu
412-268-2284

Research Interests

Integer programming. Combinatorial optimization: Packing and covering.

Books

Publications

Integer Programming

Packing and Covering

Optimality certificates for convex minimization and Helly numbers, by Amitabh Basu, Michele Conforti, Gerard Cornuejols, Robert Weismantel and Stefan Weltge, October 2016. Ideal clutters that do not pack, by Ahmad Abdi, Gerard Cornuejols and Kanstantsin Pashkovich, September 2016.
On the Rational Polytopes with Chvatal Rank 1, by Gerard Cornuejols, Dabeen Lee and Yanjun Li, November 2016. Recognizing Berge Graphs, by Maria Chudnovsky, Gerard Cornuejols, Xinming Liu, Paul Seymour and Kristina Vuskovic. Combinatorica 25 (2005) 143-186. ps version
On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvatal Rank, by Gerard Cornuejols and Dabeen Lee, October 2015. Odd Hole Recognition in Graphs of Bounded Clique Size, by Michele Conforti, Gerard Cornuejols, Xinming Liu, Kristina Vuskovic and Giacomo Zambelli. SIAM Journal on Discrete Mathematics 20 (2006) 42-48. ps version
When the Gomory-Chvatal Closure Coincides with the Integer Hull, by Gerard Cornuejols and Yanjun Li, March 2016. IPCO version: Deciding Emptyness of the Gomory-Chvatal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point. The Strong Perfect Graph Theorem, by Gerard Cornuejols. Optima 70 (2003) 2-6. ps version. French version: Seminaire Bourbaki Le Theoreme Fort des Graphes Parfaits. Published in Asterisque 311 (2007) 123-135. ps version. An earlier draft: The Strong Perfect Graph Conjecture. Proceedings of the International Congress of Mathematicians III: Invited Lectures Beijing (2002) 547-559. ps version
Cut-Generating Functions for Integer Variables, by Sercan Yildiz and Gerard Cornuejols, Mathematics of Operations Research 41 (2016) 1381-1403. Decomposing Berge Graphs Containing No Proper Wheel, Long Prism or their Complements, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Combinatorica 26 (2006) 533-558. ps version
Disjunctive Cuts for Cross-Sections of the Second-Order Cone, by Sercan Yildiz and Gerard Cornuejols. Operations Research Letters 43 (2015) 432-437. Decomposing Berge Graphs Containing Proper Wheels, by Michele Conforti, Gerard Cornuejols, Kristina Vuskovic and Giacomo Zambelli, March 2002. ps version
On the Relative Strength of Families of Intersection Cuts Arising from Pairs of Tableau Constraints in Mixed Integer Programs, by Yogesh Awate, Gerard Cornuejols, Bertrand Guenin and Levent Tuncel. Mathematical Programming A 150 (2015) 459-489. Decomposition of Odd-Hole-Free Graphs by Double Star Cutsets and 2-Joins, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Discrete Mathematics 141 (2004) 41-91. ps version
Sufficiency of Cut-Generating Functions, by Gerard Cornuejols, Laurence Wolsey and Sercan Yildiz. Mathematical Programming A 152 (2015) 643-651. Square-Free Perfect Graphs, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Journal of Combinatorial Theory B 90 (2004) 257-307. ps version
Cut-Generating Functions and S-Free Sets, by Michele Conforti, Gerard Cornuejols, Aris Daniilidis, Claude Lemarechal and Jerome Malick. Mathematics of Operations Research 40 (2015) 276-301. A Class of Berge Graphs Containing P6, by Gerard Cornuejols and Xinming Liu. Journal of Combinatorial Theory B 87 (2003) 300-330. ps version
Cutting Planes from Two-Term Disjunctions, by Pierre Bonami, Michele Conforti, Gerard Cornuejols, Marco Molinaro and Giacomo Zambelli. Operations Research Letters 41 (2013) 442-444. Graphs without Odd Holes, Parachutes or Proper Wheels: A Generalization of Meyniel Graphs and of Line Graphs of Bipartite Graphs, by Michele Conforti, Gerard Cornuejols. Journal of Combinatorial Theory B 87 (2003) 331-347. ps version
On the Safety of Gomory Cut Generators, by Gerard Cornuejols, Francois Margot and Giacomo Nannicini. Mathematical Programming Computation 5 (2013) 345-395. Perfect Graphs, Partitionable Graphs and Cutsets, by Michele Conforti, Gerard Cornuejols, Grigor Gasparyan and Kristina Vuskovic. Combinatorica 22 (2002) 19-33.
Lifting Gomory Cuts with Bounded Variables, by Gerard Cornuejols, Tamas Kis and Marco Molinaro. Operations Research Letters 41 (2013) 142-146. Even-Hole-Free Graphs Part I: Decomposition Theorem, by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuskovic. Journal of Graph Theory 39 (2002) 6-49. ps version
Combining Lift-and-Project and Reduce-and-Split, by Egon Balas, Gerard Cornuejols, Tamas Kis and Giacomo Nannicini. INFORMS Journal on Computing 25 (2013) 475-487. Even-Hole-Free Graphs Part II: Recognition Algorithm, by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuskovic. Journal of Graph Theory 40 (2002) 238-266. ps version 3. Balanced Matrices
A 3-Slope Theorem for the Infinite Relaxation in the Plane, by Gerard Cornuejols and Marco Molinaro. Mathematical Programming A 142 (2013) 83-105. Balanced Matrices, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Discrete Mathematics 306 (2006) 2411-2437. ps version
Extended Formulations in Combinatorial Optimization, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Annals of Operations Research 204 (2013) 97-143. An earlier draft appeared in 4OR - Quarterly Journal of Operations Research 8 (2010) 1-48. Bicolorings and Equitable Bicolorings of Matrices, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. MPS/SIAM Series on Optimization, The Sharpest Cut: The Impact of Manfred Padberg and His Work , Martin Groetschel ed. (2004) 33-37. ps version
How Tight is the Corner Relaxation? Insights Gained from the Stable Set Problem by Gerard Cornuejols, Carla Michini and Giacomo Nannicini. Discrete Optimization 9 (2012) 109-121. Decomposition of Balanced Matrices, by Michele Conforti, Gerard Cornuejols and M. R. Rao. Journal of Combinatorial Theory B 77 (1999) 292-406. Winner of the Fulkerson prize 2000, for best paper in Discrete Mathematics (offered jointly by the Mathematical Programming Society and the American Mathematical Society).
Intersection Cuts with Infinite Split Rank, by Amitabh Basu, Gerard Cornuejols and Francois Margot. Mathematics of Operations Research 37 (2012) 21-40. Erratum Balanced 0+-1 Matrices Part I: Decomposition, by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuskovic. Journal of Combinatorial Theory B 81 (2001) 243-274
A Counterexample to a Conjecture of Gomory and Johnson, by Amitabh Basu, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Mathematical Programming A 133 (2012) 25-38. Balanced 0+-1 Matrices Part II: Recognition Algorithm, by Michele Conforti, Gerard Cornuejols, Ajai Kapoor and Kristina Vuskovic. Journal of Combinatorial Theory B 81 (2001) 275-306
Mixed Integer NonLinear Programs featuring "On/Off" Constraints, by Hassan Hijazi, Pierre Bonami, Gerard Cornuejols and Adam Ouorou. Computational Optimization and Applications 52 (2012) 537-558. On Padberg's Conjecture about Almost Totally Unimodular Matrices, by Gerard Cornuejols and Luis F. Zuluaga. Operations Research Letters 27 (2000) 97-99.4. Ideal Matrices
Unique Minimal Liftings for Simplicial Polytopes, by Amitabh Basu, Gerard Cornuejols and Matthias Koeppe. Mathematics of Operations Research 37 (2012) 346-355. Lehman Matrices, by Gerard Cornuejols, Bertrand Guenin and Levent Tuncel. Journal of Combinatorial Theory B 99 (2009) 531-556. DOI 10.1016/j.jctb.2008.06.009 ps version
Unique Lifting of Integer Variables in Minimal Inequalities, by Amitabh Basu, Manoel Campelo, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Mathematical Programming A 141 (2013) 561-576. IPCO version: On Lifting Integer Variables in Minimal Inequalities, IPCO 2010, Lausanne, LNCS 6080 (2010) 85-95. Ideal Clutters, by Gerard Cornuejols and Bertrand Guenin. Discrete Applied Mathematics 123 (2002) 303-338. ps version
A Geometric Perspective on Lifting, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Operations Research 59 (2011) 569-577. Ideal Binary Clutters, Connectivity and a Conjecture of Seymour, by Gerard Cornuejols and Bertrand Guenin. SIAM Journal on Discrete Mathematics 15 (2002) 329-352. ps version. Winner of the SIAM Outstanding Paper Prize 2004.
Corner Polyhedron and Intersection Cuts, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Surveys in Operations Research and Management Science 16 (2011) 105-120. A Note on Dijoins, by Gerard Cornuejols and Bertrand Guenin. Discrete Mathematics 243 (2002) 213-216.
Practical Strategies for Generating Rank-1 Split Cuts in Mixed-Integer Linear Programming, by Gerard Cornuejols and Giacomo Nannicini. Mathematical Programming Computation 3 (2011) 281-318. The Packing Property, by Gerard Cornuejols, Bertrand Guenin and Francois Margot. Mathematical Programming A 89 (2000) 113-126.
Experiments with Two-Row Cuts from Degenerate Tableaux, by Amitabh Basu, Pierre Bonami, Gerard Cornuejols and Francois Margot. INFORMS Journal on Computing 23 (2011) 578-590.
Improved Strategies for Branching on General Disjunctions, by Gerard Cornuejols, Leo Liberti and Giacomo Nannicini. Mathematical Programming A 130 (2011) 225-247. Related paper: Branching on Split Disjunctions by Giacomo Nannicini, Gerard Cornuejols, Miroslav Karamanov and Leo Liberti, in Combinatorial Optimization: Methods and Applications, V. Chvatal ed., IOS Press (2011) 164-182.
Branching on General Disjunctions, by Miroslav Karamanov and Gerard Cornuejols. ps version 2005. Mathematical Programming A 128 (2011) 403-436.
A Probabilistic Analysis of the Strength of the Split and Triangle Closures, by Amitabh Basu, Gerard Cornuejols and Marco Molinaro, October 2010. IPCO 2011 version , O. Günlük and G. J. Woeginger eds., LNCS 6655 (2011) 27-38.
On the Relative Strength of Split, Triangle and Quadrilateral Cuts, by Amitabh Basu, Pierre Bonami, Gerard Cornuejols and Francois Margot. Mathematical Programming A 126 (2011) 281-314. Conference version in SODA 2009, 1220-1229.
Convex Sets and Minimal Sublinear Functions, by Amitabh Basu, Gerard Cornuejols and Giacomo Zambelli. Journal of Convex Analysis 18 (2011) 427-432. ps version
Minimal Inequalities for an Infinite Relaxation of Integer Programs, by Amitabh Basu, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. SIAM Journal on Discrete Mathematics 24 (2010) 158-168.
Maximal Lattice-free Convex Sets in Linear Subspaces, by Amitabh Basu, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Mathematics of Operations Research 35 (2010) 704-720.
Equivalence between Intersection Cuts and the Corner Polyhedron, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Operations Research Letters 38 (2010) 153-155.
Stable Sets, Corner Polyhedra and the Chvatal Closure, by Manoel Campelo and Gerard Cornuejols. Operations Research Letters 37 (2009) 375-378. previous version
On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints, by Gerard Cornuejols and Francois Margot. Mathematical Programming A 120 (2009) 429-456. ps version. Conference version in LATIN 2008, 317-328.
Minimal Valid Inequalities for Integer Constraints, by Valentin Borozan and Gerard Cornuejols. Mathematics of Operations Research 34 (2009) 538-546. ps version
Polyhedral Approaches to Mixed Integer Linear Programming, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. 50 Years of Integer Programming edited by Michael Juenger, Springer Verlag (2009) 343-386. ps version
A Feasibility Pump for Mixed Integer Nonlinear Programs, by Pierre Bonami, Gerard Cornuejols, Andrea Lodi and Francois Margot. Mathematical Programming A 119 (2009) 331-352.
An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs, by Pierre Bonami, Andreas Waechter, Lorenz Biegler, Andrew Conn, Gerard Cornuejols, Ignacio Grossmann, Carl Laird, Jon Lee, Andrea Lodi, Francois Margot and Nicolas Sawaya. Discrete Optimization 5 (2008) 186-204. The most frequently cited paper published in Discrete Optimization 2005-2010.
Valid Inequalities for Mixed Integer Linear Programs, by Gerard Cornuejols. Mathematical Programming B 112 (2008) 3-44. ps version
Projected Chvatal-Gomory Cuts for Mixed Integer Linear Programs, by Pierre Bonami, Gerard Cornuejols, Sanjeeb Dash, Matteo Fischetti and Andrea Lodi. Mathematical Programming A 113 (2008) 241-257. ps version
A Note on the MIR Closure, by Pierre Bonami and Gerard Cornuejols. Operations Research Letters 36 (2008) 4-6.
Revival of the Gomory Cuts in the 1990's, by Gerard Cornuejols. Annals of Operations Research 149 (2007) 63-66. ps version
Early Estimates of the Size of Branch-and-Bound Trees, by Gerard Cornuejols, Miroslav Karamanov and Yanjun Li. INFORMS Journal on Computing 18 (2006) 86-96. ps version
A Convex-Analysis Perspective on Disjunctive Cuts, by Gerard Cornuejols and Claude Lemarechal, Mathematical Programming A 106 (2006) 567-586. ps version
Reduce-and-Split Cuts: Improving the Performance of Mixed Integer Gomory Cuts, by Kent Andersen, Gerard Cornuejols and Yanjun Li. Management Science 51 (2005) 1720-1732. ps version
Split Closure and Intersection Cuts, by Kent Andersen, Gerard Cornuejols and Yanjun Li. Mathematical Programming A 102 (2005) 457-493. ps version; conference version Published in IPCO 2002 (W.J. Cook and A.S. Schulz eds.), Lecture Notes in Computer Science 2337 (2002) 127-144.
K-Cuts: A Variation of Gomory Mixed Integer Cuts from the LP Tableau, by Gerard Cornuejols, Yanjun Li and Dieter Vandenbussche. INFORMS Journal on Computing 15 (2003) 385-396. ps version
A Connection Between Cutting Plane Theory and the Geometry of Numbers, by Gerard Cornuejols and Yanjun Li. Mathematical Programming A 93 (2002) 123-127. ps version
On the Rank of Mixed 0,1 Polyhedra, by Gerard Cornuejols and Yanjun Li. Mathematical Programming A 91 (2002) 391-397.
Elementary Closures for Integer Programs, by Gerard Cornuejols and Yanjun Li. Operations Research Letters 28 (2001) 1-8.

Course Material