Ted Ralphs

There is a newer version of this course here

Miscellaneous Handouts

• Course Syllabus

Lecture Slides

• Branch and Bound
• Lecture 1: Introduction
• Lecture 2: Branch and Bound.
• Lecture 3: Relaxation.
• Lecture 4: Branching.
• Advanced Bounding Techniques
• Lecture 5: Decomposition.
• Lecture 6: Cutting Plane Methods.
• Putting it All Together: Search
• Lecture 7: Search Strategies.
• Lecture 8: Branch and Cut.
• Lecture 9: Branch and Price.

Reading Room

• R. Gomory (1958), Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Monthly 24, 275-278.
• 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.
• 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. Luebbecke and J. Desrosier (2005). Selected Topics in Column Generation.
• F. Vanderbeck and L. Wolsey (2009). Reformulation and Decomposition of Integer Programs.
• 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. Villeneuve, J. Desrosiers, M. Luebbecke, F. Soumis (2003). On Compact Formulations for Integer Programs Solved by Column Generation.
• 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).
• L. Liberti (2008), Reformulations in Mathematical Programming: Symmetry.
• F. Margot (2008), Symmetry in Integer Linear Programming.
• T. Berthold (2006), Primal Heuristics for Mixed Integer Programs.
• A. Martin (1999), Integer Programs with Block Structure.

Reference Texts

• Course Text: 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.