Gerard Cornuejols

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

Tepper School Room 4107
gc0v@andrew.cmu.edu
412-268-2284

Research Interests

Integer programming. Combinatorial optimization: Packing and covering.

Books

Publications

Optimization

Packing and Covering

Reducing the Chvatal Rank through Binarization, by Gerard Cornuejols and Vrishabh Patil (March 2024) Approximately Packing Dijoins via Nowhere-Zero Flows, by Gerard Cornuejols, Siyue Liu, and R. Ravi (March 2024)
Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization, by Gerard Cornuejols and Yatharth Dubey (November 2023) Arc Connectivity and Submodular Flows in Digraphs, by Ahmad Abdi, Gerard Cornuejols, and Giacomo Zambelli (revised October 2023)
Dyadic Linear Programming and Extensions, by Ahmad Abdi, Gerard Cornuejols, Bertrand Guenin and Levent Tuncel (September 2023) On Packing Dijoins in Digraphs and Weighted Digraphs, by Ahmad Abdi, Gerard Cornuejols, and Michael Zlatin, SIAM Journal on Discrete Mathematics 37 (2023) 2417-2461.
Total Dual Dyadicness and Dyadic Generating Sets, by Ahmad Abdi, Gerard Cornuejols, Bertrand Guenin, and Levent Tuncel (January 2023). To appear in Mathematical Programming. IPCO version (February 2022). Testing Idealness in the Filter Oracle Model, by Ahmad Abdi, Gerard Cornuejols, Bertrand Guenin, and Levent Tuncel. Operations Research Letters 50 (2022) 753-755.
Portfolio Optimization in the Presence of Estimation Errors on the Expected Asset Returns, by Gerard Cornuejols, Ozgun Elci, and Matthias Koeppe (July 2022). A Min-Max Theorem for Clean Tangled Clutters, by Ahmad Abdi and Gerard Cornuejols (January 2022)
Egon Balas: Pioneer in Integer Programming, by Gerard Cornuejols. SIAG/OPT Views and News 27 (October 2019) 7-9. On Dyadic Fractional Packings of T-joins, by Ahmad Abdi, Gerard Cornuejols, and Zuzanna Palion. SIAM Journal on Discrete Mathematics 36 (2022) 2445-2451.
Computational Aspects of Baysian Solution Estimators in Stochastic Optimization, by Danial Davarnia, Burak Kocuk and Gerard Cornuejols. INFORMS Journal on Optimization 2 (2020) 256-272. Clean Clutters and Dyadic Fractional Packings, by Ahmad Abdi, Gerard Cornuejols, Bertrand Guenin, and Levent Tuncel. SIAM Journal on Discrete Mathematics 36 (2022) 1012-1037.
From Estimation to Optimization via Shrinkage, by Danial Davarnia and Gerard Cornuejols, Operations Research Letters 45 (2017) 642-646. Clean Tangled Clutters, Simplices and Projective Geometries, by Ahmad Abdi, Gerard Cornuejols and Matt Superdock. Journal of Combinatorial Theory B 46 (2022) 60-92.
Incorporating Black-Litterman Views in Portfolio Construction when Stock Returns are a Mixture of Normals, by Burak Kocuk and Gerard Cornuejols. Omega 91 (2020) 1-12. data. A New Inifinite Class of Ideal Minimally Non-Packing Clutters, by Ahmad Abdi, Gerard Cornuejols and Matt Superdock, Discrete Mathematics 344 (2021) 1-13.
On the Rational Polytopes with Chvatal Rank 1, by Gerard Cornuejols, Dabeen Lee and Yanjun Li. Mathematical Programming 179 (2020) 21-46. Idealness of k-Wise Intersecting Families, by Ahmad Abdi, Gerard Cornuejols, Tony Huynh and Dabeen Lee. Mathematical Programming192 (2022) 29-50. erratum. Extended abstract IPCO 2020, London, UK, LNCS 12125 (2020) 1-12.
When the Gomory-Chvatal Closure Coincides with the Integer Hull, by Gerard Cornuejols and Yanjun Li. Operations Research Letters 46 (2018) 251-256. IPCO version: Deciding Emptyness of the Gomory-Chvatal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point. Intersecting Restrictions in Clutters, by Ahmad Abdi, Gerard Cornuejols and Dabeen Lee, Combinatorica 40 (2020) 605-623.
On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvatal Rank, by Gerard Cornuejols and Dabeen Lee. Mathematical Programming 172 (2018) 467-503. IPCO version. Identically Self-Blocking Clutters, by Ahmad Abdi, Gerard Cornuejols and Dabeen Lee. IPCO 2019, Ann Arbour, MI, LNCS 11480 (2019) 1-12.
Optimality Certificates for Convex Minimization and Helly Numbers, by Amitabh Basu, Michele Conforti, Gerard Cornuejols, Robert Weismantel and Stefan Weltge. Operations Research Letters 45 (2017) 671-674. Resistant Sets in the Unit Hypercube, by Ahmad Abdi, Gerard Cornuejols and Dabeen Lee. Mathematics of Operations Research 46 (2021) 82-114.
Cut-Generating Functions for Integer Variables, by Sercan Yildiz and Gerard Cornuejols. Mathematics of Operations Research 41 (2016) 1381-1403. The Max-Flow Min-Cut Property and +-1-Resistant Sets, by Ahmad Abdi, Gerard Cornuejols. Discrete Applied Mathematics 289 (2021) 455-476.
Disjunctive Cuts for Cross-Sections of the Second-Order Cone, by Sercan Yildiz and Gerard Cornuejols. Operations Research Letters 43 (2015) 432-437. Idealness and 2-Resistant Sets, by Ahmad Abdi and Gerard Cornuejols. Operations Research Letters 47 (2019) 358-362.
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. Cuboids, A Class of Clutters, by Ahmad Abdi, Gerard Cornuejols, Natalia Guricanova and Dabeen Lee. Journal of Combinatorial Theory B 142 (2020) 144-209. Extended Abstract.
Sufficiency of Cut-Generating Functions, by Gerard Cornuejols, Laurence Wolsey and Sercan Yildiz. Mathematical Programming A 152 (2015) 643-651. Ideal Clutters that Do Not Pack, by Ahmad Abdi, Kanstantsin Pashkovich and Gerard Cornuejols. Mathematics of Operations Research 43 (2018) 533-553.
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. Recognizing Berge Graphs, by Maria Chudnovsky, Gerard Cornuejols, Xinming Liu, Paul Seymour and Kristina Vuskovic. Combinatorica 25 (2005) 143-186. 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. 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
On the Safety of Gomory Cut Generators, by Gerard Cornuejols, Francois Margot and Giacomo Nannicini. Mathematical Programming Computation 5 (2013) 345-395. 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
Lifting Gomory Cuts with Bounded Variables, by Gerard Cornuejols, Tamas Kis and Marco Molinaro. Operations Research Letters 41 (2013) 142-146. 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
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. Decomposing Berge Graphs Containing Proper Wheels, by Michele Conforti, Gerard Cornuejols, Kristina Vuskovic and Giacomo Zambelli, March 2002. ps version
A 3-Slope Theorem for the Infinite Relaxation in the Plane, by Gerard Cornuejols and Marco Molinaro. Mathematical Programming A 142 (2013) 83-105. 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
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. Square-Free Perfect Graphs, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Journal of Combinatorial Theory B 90 (2004) 257-307. 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. A Class of Berge Graphs Containing P6, by Gerard Cornuejols and Xinming Liu. Journal of Combinatorial Theory B 87 (2003) 300-330. ps version
Intersection Cuts with Infinite Split Rank, by Amitabh Basu, Gerard Cornuejols and Francois Margot. Mathematics of Operations Research 37 (2012) 21-40. Erratum 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
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. Perfect Graphs, Partitionable Graphs and Cutsets, by Michele Conforti, Gerard Cornuejols, Grigor Gasparyan and Kristina Vuskovic. Combinatorica 22 (2002) 19-33.
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. 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
Unique Minimal Liftings for Simplicial Polytopes, by Amitabh Basu, Gerard Cornuejols and Matthias Koeppe. Mathematics of Operations Research 37 (2012) 346-355. 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
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. Balanced Matrices, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Discrete Mathematics 306 (2006) 2411-2437. ps version
A Geometric Perspective on Lifting, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Operations Research 59 (2011) 569-577. 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
Corner Polyhedron and Intersection Cuts, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Surveys in Operations Research and Management Science 16 (2011) 105-120. 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).
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. 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
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. 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
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. 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
Branching on General Disjunctions, by Miroslav Karamanov and Gerard Cornuejols. ps version 2005. Mathematical Programming A 128 (2011) 403-436. 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
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. Ideal Clutters, by Gerard Cornuejols and Bertrand Guenin. Discrete Applied Mathematics 123 (2002) 303-338. ps version
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. 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.
Convex Sets and Minimal Sublinear Functions, by Amitabh Basu, Gerard Cornuejols and Giacomo Zambelli. Journal of Convex Analysis 18 (2011) 427-432. ps version A Note on Dijoins, by Gerard Cornuejols and Bertrand Guenin. Discrete Mathematics 243 (2002) 213-216.
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. The Packing Property, by Gerard Cornuejols, Bertrand Guenin and Francois Margot. Mathematical Programming A 89 (2000) 113-126.
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