Gerard Cornuejols, professor, Carnegie Mellon University.

---

Course Material


• Optimization Methods in Finance 2007, by Gerard Cornuejols and Reha Tutuncu. Published by Cambridge University Press.
  http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521861700
  
• Combinatorial Optimization: Packing and Covering Spring 2000. Published by SIAM (2001) in the CBMS-NSF Regional Conference Series in Applied Mathematics CBMS 74. ps version
  The two conjectures in Chapter 3 were solved by Maria Chudnovsky, Robin Thomas, Neil Robertson and Paul Seymour (2002). Conjecture 4.14 in Chapter 4 was solved by Jonathan Wang (2010). The three conjectures in Chapter 9 were solved by Maria Chudnovsky and Paul Seymour (2006). Twelve are still unsolved!
  
• Slides Cut Generating Functions
  
• Slides A Geometric View on Integer Lifting
  
• Slides Multi-Row Cuts and Integer Lifting
  
• Slides Corner Polyhedron, Intersection Cuts and Maximal Lattice-Free Convex Sets
  
• Slides Lehman Matrices
  
  Research Papers
  
  1. Integer Programming
  
• 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, March 2013.
  
• Sufficiency of Cut-Generating Functions, by Gerard Cornuejols, Laurence Wolsey and Sercan Yildiz, April 2013.
  
• Cut-Generating Functions and S-Free Sets, by Michele Conforti, Gerard Cornuejols, Aris Daniilidis, Claude Lemarechal and Jerome Malick, February 2013.
  
• Cutting Planes from Two-Term Disjunctions, by Pierre Bonami, Michele Conforti, Gerard Cornuejols, Marco Molinaro and Giacomo Zambelli, February 2013.
  
• On the Safety of Gomory Cut Generators, by Gerard Cornuejols, Francois Margot and Giacomo Nannicini, May 2012, revised February 2013.
  
• Lifting Gomory Cuts with Bounded Variables, by Gerard Cornuejols, Tamas Kis and Marco Molinaro. Operations Research Letters 41 (2013) 142-146.
  
• Combining Lift-and-Project and Reduce-and-Split, by Egon Balas, Gerard Cornuejols, Tamas Kis and Giacomo Nannicini, revised July 2011. To appear in INFORMS Journal on Computing.
  
• A 3-Slope Theorem for the Infinite Relaxation in the Plane, by Gerard Cornuejols and Marco Molinaro. To appear in Mathematical Programming. DOI 10.1007/s10107-012-0562-7.
  
• Extended Formulations in Combinatorial Optimization, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli, October 2012. To appear in Annals of Operations Research. An earlier draft appeared in 4OR - Quarterly Journal of Operations Research 8 (2010) 1-48.
  
• 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.
  
• Intersection Cuts with Infinite Split Rank, by Amitabh Basu, Gerard Cornuejols and Francois Margot. Mathematics of Operations Research 37 (2012) 21-40. Erratum
  
• 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.
  
• Mixed Integer NonLinear Programs featuring "On/Off" Constraints: Convex Analysis and Applications, by Hassan Hijazi, Pierre Bonami, Gerard Cornuejols and Adam Ouorou. Computational Optimization and Applications 52 (2012) 537-558.
  
• Unique Minimal Liftings for Simplicial Polytopes, by Amitabh Basu, Gerard Cornuejols and Matthias Koeppe. Mathematics of Operations Research 37 (2012) 346-355.
  
• Unique Lifting of Integer Variables in Minimal Inequalities, by Amitabh Basu, Manoel Campelo, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. To appear in Mathematical Programming DOI 10.1007/s10107-012-0560-9. IPCO version: On Lifting Integer Variables in Minimal Inequalities, IPCO 2010, Lausanne, LNCS 6080 (2010) 85-95.
  
• A Geometric Perspective on Lifting, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Operations Research 59 (2011) 569-577.
  
• Corner Polyhedron and Intersection Cuts, by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli. Surveys in Operations Research and Management Science 16 (2011) 105-120.
  
• 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.
  
• 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.
  
  2. Perfect Graphs
  
• Recognizing Berge Graphs, by Maria Chudnovsky, Gerard Cornuejols, Xinming Liu, Paul Seymour and Kristina Vuskovic. Combinatorica 25 (2005) 143-186. ps version
  
• 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
  
• 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
  
• 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
  
• Decomposing Berge Graphs Containing Proper Wheels, by Michele Conforti, Gerard Cornuejols, Kristina Vuskovic and Giacomo Zambelli, March 2002. ps version
  
• 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
  
• Square-Free Perfect Graphs, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Journal of Combinatorial Theory B 90 (2004) 257-307. ps version
  
• A Class of Berge Graphs Containing P6, by Gerard Cornuejols and Xinming Liu. Journal of Combinatorial Theory B 87 (2003) 300-330. ps version
  
• 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
  
• Perfect Graphs, Partitionable Graphs and Cutsets, by Michele Conforti, Gerard Cornuejols, Grigor Gasparyan and Kristina Vuskovic. Combinatorica 22 (2002) 19-33.
  
• 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
  
• 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
  
• Balanced Matrices, by Michele Conforti, Gerard Cornuejols and Kristina Vuskovic. Discrete Mathematics 306 (2006) 2411-2437. ps version
  
• 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
  
• 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).
  
• 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
  
• 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
  
• 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
  
• 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
  
• Ideal Clutters, by Gerard Cornuejols and Bertrand Guenin. Discrete Applied Mathematics 123 (2002) 303-338. ps version
  
• 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.
  
• A Note on Dijoins, by Gerard Cornuejols and Bertrand Guenin. Discrete Mathematics 243 (2002) 213-216.
  
• The Packing Property, by Gerard Cornuejols, Bertrand Guenin and Francois Margot. Mathematical Programming A 89 (2000) 113-126.