IE418 -- Integer Programming

This class is being taught by Prof. Jeff Linderoth

News

Introductory Material

Course Syllabus

Lecture Notes

Lecture 1 -- January 19, 2005
Lecture 2 -- January 24--26, 2005
Lecture 3 -- January 31, 2005
Lecture 4 -- February 2, 2005
Lecture 5 -- February 7, 2005
Lecture 6 -- February 9, 2005
Lecture 7 -- February 14, 2005
Lecture 8. Complexity. February 16, 2005
Lecture 9. Complexity, revisited. February 21, 2005
Lecture 10. Complexity, reductions. February 23, 2005
Lecture 11. Polyhedra---First Definitions. March 21, 2005
Lecture 12. Polyhedra---Facets. March 23, 2005
Lecture 13. Polyhedra---Facets, cont.. March 28, 2005
Lecture 14. Separation = Optimization. March 30, 2005
Lecture 15. Knapsack Covers. April 4, 2005.
Lecture 16. Lifting. April 6, 2005.
Lecture 17. Lifting and Separation. April 13, 2005.
Lecture 18. Gomory Cuts. Mixed Integer Rounding. April 18, 2005.
Lecture 19. Decomposition. April 20, 2005.
Lecture 20. Decomposition and Hodgepodge. April 25, 2005.

Assignments

Problem Set 1 -- Due February 9, 2005
Problem Set 2 -- Due February 23, 2005 Some helpful MINTO code for problem 5
Problem Set 3 -- Due April 4, 2005
Problem Set 4 and 5 -- Due April 27, 2005

Papers

BRANCH.pdf

J. T. Linderoth and M. W. P. Savelsbergh, "A Computational Study of Branch and Bound Search Strategies for Mixed Integer Programming," INFORMS Journal on Computing, 11 (1999) pp. 173-187.

IP-SOFTWARE.pdf

A. Atamturk and M. W. P. Savelsbergh, "Integer Programming Software Systems", Annals of Operations Research, forthcoming.

MILP04.pdf

J. T. Linderoth and T. K. Ralphs, ``Noncommercial Software for Mixed-Integer Linear Programming'', Technical Report 04T-023, Department of Industrial and Systems Engineering, Lehigh University, December, 2004.

cover-pack.pdf

Research Report BCOL.03.02, IEOR, University of California at Berkeley. February 2003. Revised June 2003. Forthcoming in Annals of Operations Research

AggRounding Paper
H. Marchand and L. Wolsey, "Aggregation and Mixed Integer Rounding to Solve MIPs", Operations Research 49 (2001) pp. 363-371.

PreprocessingProbing.pdf
M. Savelsbergh, "Preprocessing and Probing Techniques for Mixed Integer Programming problems", INFORMS Journal on Computing, 6 (1994), pp.445-454.

BranchAndPrice.pdf
C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, P.H. Vance, "Branch-and-Price: Column Generation for Huge Integer Programs," Operations Research 46 (1998), pp. 316-329.

UnifiedDantzigWolfe.pdf
F. Vanderbeck and M.W.P. Savelsbergh A Generic View of Dantzig-Wolfe Decomposition for Integer Programming. Submitted to Operations Research Letters, 2005.

Supplementary Materials

Computational IP for Dummies. A lecture I gave at Argonne National Lab in the Summer of 1999.
Cool Title Slide from Dummies lecture. I wasted a whole morning making this!
Harvey Greenberg's MIP Sites List Harvey Greenberg's MIP Course Page