Ted Ralphs

Miscellaneous Handouts

• Course Syllabus

Schedule of Lectures and Slides

• Introduction
  • Introduction
  • Lecture 1: What is Integer Programming?
  • Lecture 2: Formulating Integer Programs
  • Lecture 3: Alternative Formulations
  • Lecture 4: Linear Algebra and Convexity
  • Lecture 5: Polyhedra and Dimension
  • Lecture 6: The Fundamental Theorem
• Enumerative Methods and Disjunction
  • Lecture 7: Introduction to Branch and Bound
  • Lecture 8: Duality and Optimality Conditions
  • Lecture 9: Branching and Disjunction
  • Lecture 10: Relaxation
  • Lecture 11: Search
• Polyhedral Theory and Convexification
  • Lecture 12: The Cutting Plane Method and the Separation Problem
  • Lecture 13: Elementary Inequalities and Rounding
  • Lecture 14: Disjunctive Inequalities
  • Lecture 15: Split Inequalities and Closures
  • Lecture 17: Structured Inequalities and Lifting
  • Lecture 18: Column Generation and the Pricing Problem
• Computational Methods
  • Lecture 19: Principles of Decomposition
  • Lecture 20: Constraint Decomposition
  • Lecture 21: Variable Decomposition
  • Lecture 22: Branch and Cut and Price
  • Lecture 23: Preprocessing
  • Lecture 24: Primal Heuristics
  • Lecture 25: Symmetry
  • Lecture 26: Numerics
• Complexity
  • Lecture 27: Introduction to Computational Complexity
  • Lecture 28: Certificates and Complexity Classes
  • Lecture 29: Easy Integer Programs and Integral Polyhedra
  • Lecture 30: Combinatorial Algorithms for Integer Programs

Assignments

See Google Classroom

Software

• GiMPy
• GrUMPy
• CuPPy
• DIPPy
• Pydot
• PyPolyhedron
• Graphviz
• cyLP
• yaposib
• PuLP
• SYMPHONY

Instance Gallery

Click here for instance gallery!

Models/Scripts From Lecture

• facility_location_pulp.py
• facility_location.py
  • facility_ex1.py
  • facility_test1.py
  • facility_test2.py
  • facility_test6.py
• gap.py
  • gap0515-2.dat

Reading Room

• History and Overview
• K. L. Hoffman and T. K. Ralphs (2011), Integer and Combinatorial Optimization.
• E.L. Johnson and G.L. Nemhauser (2000), Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
• R. Gomory (2002). Early Integer Programming.
• R.E Bixby, M. Fenelon, Z. Gu, E. Rothberg (2004) Mixed-Integer Programming: A Progress Report.
• A. Schrijver (2005). On the History of Combinatorial Optimization (till 1960).
• W. Cook (2009). Fifty-Plus Years of Combinatorial Integer Programming.
• R. Bixby (2010). A Brief History of Linear and Mixed-Integer Programming Computation.
• Modeling and Formulation
  • Robert Bosch and Michael Trick.
  • AIMMS Guide.
  • Michael Trick.
  • Cole Smith and Caner Taskin.
  • J.P. Vielma
• Theory of Valid Inequalities.
• G. Dantzig, R. Fulkerson and S. Johnson (1954). Solution of a Large-Scale Traveling-Salesman Problem.
• H.M. Markowitz and A.S. Manne (1957). On the Solution of Discrete Programming Problems
• R. Gomory (1958), Outline of an Algorithm for Integer Solutions to Linear Programs.
• E. Balas and R.G. Jeroslow (1980) Strengthening cuts for mixed integer programs.
• E.A. Boyd (1994), Fenchel cutting planes for integer programs.
• K. Aardal and C. van Hoesel(1996). Polyhedral Techniques in Combinatorial Optimization I: Theory. Statistica Neerlandica, 50:3-26, 1996.
• E. Balas, S. Ceria, G. Cornuéjols, and N. Natraj (1996). Gomory Cuts Revisited.
• S. Ceria, C. Cordier, H. Marchand & L.A. Wolsey (1998) Cutting planes for integer programs with general integer variables.
• Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (2000). Sequence Independent Lifting. Journal of Combinatorial Optimization 4, 109-129.
• J. Owens and S. Mehrotra (2001), A Disjunctive Cutting Plane Procedure for General Mixed-integer Linear Programs.
• M. Perregaard (2003), Generating Disjunctive Cuts for Mixed Integer Programs.
• E. Balas and M. Perregaard (2003), A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming.
• A. Caprara and A.N. Letchford (2003), On the Separation of Split Cuts and Related Inequalities.
• K. Anderson and G. Cornuejols (2005). Split Closure and Intersection Cuts.
• G. Cornuejols (2006). Valid Inequalities for Mixed Integer Linear Programs.
• P. Bonami (2010), On Optimizing Over Lift-And-Project Closures.
• M. Conforti, G. Cornuejols, and G. Zambelli, Corner Polyhedra and Intersection Cuts.
• M. Conforti, G. Cornuejols, S. Yildiz, and G. Zambelli, (2015) Cutting Planes in Integer Programming.
• Preprocessing and Conflict Analysis
  • A. Atamturk, G. Nemhauser, and M.W.P. Savelsburgh, Conflict Graphs in Solving Integer Programming Problems
  • T. Achterburg Conflict Analysis in Mixed Integer Programming
  • M.W.P. Savelsbergh (1994). Preprocessing and Probing for Mixed Integer Programming Problems. ORSA J. on Computing 6, 445-454.
  • T. Achterberg, R.E. Bixby, Z. Gu, E Rothberg, And D. Weninger, Presolving Reductions in Mixed Integer Programming
• Reformulation and Decomposition
  • F. Vanderbeck and L. Wolsey (2009). Reformulation and Decomposition of Integer Programs.
  • T. Ralphs and M. Galati, Decomposition in Integer Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005).
  • D. Villeneuve, J. Desrosiers, M. Luebbecke, F. Soumis (2003). On Compact Formulations for Integer Programs Solved by Column Generation.
  • L. Liberti (2008), Reformulations in Mathematical Programming: Symmetry.
• Branch and Cut
  • A. H. Land and A. G. Doig (1960). An Automatic Method of Solving Discrete Programming Problems
  • M. W. Padberg and G. Rinaldi (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33, 60–100.
  • A. Martin (2001), Computational Issues for Branch-and-Cut Algorithms. Computational Combinatorial Optimization, M. Juenger and D. Naddef, eds., 1-25.
  • J.T. Linderoth and T.K. Ralphs (2005), Noncommercial Software for Mixed-Integer Linear Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005), 253.
  • W. Cook, R. Fukusawa, and G. Goycoolea, Choosing the Best Cuts
  • K. Wolter Implementations of Cutting Plane Separators for Mixed Integer Programs
  • K. Aardal and C. van Hoesel. Polyhedral Techniques in Combinatorial Optimization II: Applications and Computations. Statistica Neerlandica, 50:3-26, 1996.
• Branch and Price
  • M. Luebbecke and J. Desrosier (2005). Selected Topics in Column Generation.
  • C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, P.H. Vance (1998). Branch-and-Price: Column Generation for Huge Integer Programs. Operations Research 46, 316-329.
  • D.M. Ryan and B.A. Foster (1981). An Integer Programming Approach to Scheduling.
• Miscellaneous Computational Issues
  • S.S. Dey and M. Molinaro (2018). Theoretical Challenges Towards Cutting-plane Selection.
  • J.T. Linderoth and M.W.P. Savelsbergh (1999). Computational Study of Search Strategies for Mixed Integer Programming. INFORMS J. on Computing 11, 173-187.
  • T. Acterburg, T. Koch, and A. Martin, Branching Rules Revisited. Operations Research Letters 33 (2005), 42-54.
  • T. Berthold Primal Heuristics for Mixed Integer Programs
  • F. Margot (2008), Symmetry in Integer Linear Programming.
  • A. Martin (1999), Integer Programs with Block Structure.
  • M. Karamanov and G. Cornuejols, Branching on General Disjunctions.
• K. Aardal, R. Weismantel, and L. Wolsey. Non-standard Approaches to Integer Programming. Discrete Applied Mathematics 123 (2002), 5-74.
• T. Koch, et al. (2011), MIPLIB 2010.

Reference Texts

• Course Text: Integer Programming, M. Conforti, G. Cornuejols, and G. Zambelli, (2015).
• Constraint Integer Programming, T. Achterberg (2007).
• Integer and Combinatorial Optimization, G.L. Nemhauser and L.A. Wolsey, Wiley (1988).
• Integer Programming L.A. Wolsey, Wiley (1998).
• Theory of Linear and Integer Programming A. Schrijver, Wiley.
• Discrete Optimization R.G. Parker and R.L. Rardin, Academic Press.
• Optimization Over Integers, D. Bertsimas and R. Weismantel.
• Introduction to Linear Optimization, D. Bertsimas and J. Tsitsiklis.
• AMPL: A Modeling Language for Math Programming R. Fourer, D. M. Gay, B. W. Kernighan.
• Mathematics of Operations Research W.H. Marlow.
• Computers and Intractability: A Guide to the Theory of NP-completeness M. Garey and D. Johnson
• Computer Solution of Linear Algebraic Systems G. Forsythe and C. Moler
• Computer Methods for Mathematical Computations G. Forsythe, M.A. Malcolm, and C. Moler.
• Geometric Algorithms and Combinatorial Optimization M Groetschel, L. Lovasz, and A. Schrijver.

AMPL Pointers

• AMPL Web site
• AMPL Book: Chapter 1
• A Modeling Language for Mathematical Programming
• Submitting models over the Web
• AMPL in Action (Case Studies using AMPL)
• New Features Page (useful reference)
• List of built-in suffixes
• AMPL/CPLEX Reference Guide

Dippy/PuLP Pointers

• PuLP home page
• Dippy home page
• Python Tutorial

Guides and Pointers on the Web

• INFORMS Resource Page–a big collection of OR links
• NEOS Guide–a good overview of optimization
• Mathematical Programming Glossary
• John Mitchell’s Optimization Pointers

On-line Tutorials, Case Studies, and Interactive Optimization

• Short Course on Modeling and the COIN-OR Optimization Suite
• IFORS tutORial Project
• NEOS Server–solve optimization problems over the Web
• NEOS Case Studies–includes an interactive version of the Diet Problem
• Math Programming in Action
• Operations Research Models and Methods — a fantastic on-line introduction to OR including Excel add-ins
• The Remote Interactive Optimization Testbed (RIOT) Page
• Open Solver–an Excel plug-in for solving optimization problems.
• J.E. Beaseley’s OR Notes
• AMPL in Action (Case Studies using AMPL)