IE 418: Integer Programming
Miscellaneous Handouts
Lecture Slides
- Introduction
- Introduction
- Lecture 1: What is Integer Programming?
- Lecture 2: Formulating Integer Programs.
- Lecture 3: Linear Algebra and Convexity.
- Lecture 4: Polyhedra and Dimension.
- Complexity
- Lecture 5: Introduction to Computational Complexity.
- Lecture 6: Certificates and Complexity Classes.
- Lecture 7: Easy Integer Programs.
- Lecture 8: Integral Polyhedra.
- Lecture 9: Combinatorial Algorithms for Integer Programs.
- Computational Methods
- Lecture 10: Introduction to Branch and Bound.
- Lecture 11: Relaxation.
- Lecture 12: Duality.
- Lecture 13: Decomposition Methods.
- Lecture 14: Branching Methods.
- Lecture 15: Search Strategies.
- Polyhedral Theory
- Lecture 16: Describing Polyhedra.
- Lecture 17: Valid Inequalities.
- Lecture 18: Valid Inequalities Based on Disjunctions.
- Lecture 19: Strong Valid Inequalities and Lifting.
- Lecture 20: Structured Inequalities.
- Advanced Computational Methods
- Lecture 21: Branch and Cut.
- Lecture 22: Branch and Price.
- Lecture 23: Advanced Topics.
- Lecture 24: Advanced Topics.
Assignments
Reading Room
- J.T. Linderoth and T.K. Ralphs, Noncommercial Software for Mixed-Integer Linear Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005), 253.
- A. Martin. Computational Issues for Branch-and-Cut Algorithms. Computational Combinatorial Optimization, M. Juenger and D. Naddef, eds. (2001), 1-25.
- 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.
- M.W.P. Savelsbergh (1994). Preprocessing and Probing for Mixed Integer Programming Problems. ORSA J. on Computing 6, 445-454.
- M.W.P. Savelsbergh (2001). Branch-and-Price: Integer Programming with Column Generation. Encyclopedia of Optimization (C. Floudas, P. Pardalos, Eds.).
- 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.
- 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.
- G. Cornuejols (2006). Valid Inequalities for Mixed Integer Linear Programs.
- K. Aardal and C. van Hoesel(1996). Polyhedral Techniques in Combinatorial Optimization I: Theory. Statistica Neerlandica, 50:3-26, 1996.
- K. Aardal and C. van Hoesel. Polyhedral Techniques in Combinatorial Optimization II: Applications and Computations. Statistica Neerlandica, 50:3-26, 1996.
- K. Aardal, R. Weismantel, and L. Wolsey. Non-standard Approaches to Integer Programming. Discrete Applied Mathematics 123 (2002), 5-74.
- Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (2000). Sequence Independent Lifting . Journal of Combinatorial Optimization 4, 109-129.
- T. Acterburg, T. Koch, and A. Martin, Branching Rules Revisited. Operations Research Letters 33 (2005), 42-54.
- M. Karamanov and G. Cornuejols, Branching on General Disjunctions.
- T. Achterburg Conflict Analysis in Mixed Integer Programming
- T. Ralphs and M. Galati, Decomposition in Integer Programming, in Integer Programming: Theory and Practice, John Karlof, ed. (2005).
Reference Texts
- Course Text: Integer Programming L.A. Wolsey, Wiley (1998).
- Integer and Combinatorial Optimization, G.L. Nemhauser and L.A. Wolsey, Wiley (1988).
- 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.
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
Guides and Pointers on the Web
- Michael Trick’s Operations Research Page — an amazing collection of OR links
- NEOS Guide — a good overview of optimization
- e-Optimization.com
- Harvey Greenburg’s Courseware Page
- Harvey Greenburg’s Mathematical Programming Glossary
- John Mitchell’s Optimization Pointers
On-line Tutorials, Case Studies, and Interactive Optimization
- 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
- On-line MPL Tutorial
- Tutorial on Spreadsheet Optimization
- The Remote Interactive Optimization Testbed (RIOT) Page
- J.E. Beaseley’s OR Notes
- AMPL in Action (Case Studies using AMPL)
- On-line Graphical LP Solver
- NEOS Java Graphical LP Solver
