| Week | Topics and Slides | Resources |
|---|---|---|
| 14 | Introduction, Farkas, Interior Point Methods | [GRB], [HL, sc 8.4], [MG, sc 7.2], [V, ch 21]; [NW] |
| LP Practical Guidelines, Sifting | [KN1], [BGLMS, sc 3] | |
| Practice | Sheet 1; sol | |
| 15 | MILP Practical Guidelines; Presolving; Modeling | [KN2], [ABGRW], [Wi, ch7,9,10] or [GRB, modeling 2] |
| MILP Formulations for Traveling Salesman Problem | [P] or [DFJ] or [MTZ] or [A] or [ABCC] or [OAL]; [OS] [Talk] | |
| Practice on TSP | Sheet 2; sol | |
| 16 | Lazy Constraints for TSP | Sheet 3; sol |
| Rounding up the practice on TSP + Dantzig Wolfe decomposition and Delayed Column Generation | [GIT]; [BGLMS, sc 3]; [Wo ch 11 in LMS]; [LD] | |
| Delayed Column Generation; Dual Bounds in Column Generation | [Wo ch 11 in LMS] | |
| 17 | Practice on CG | Sheet 4; |
| Vehicle Routing: Compact models; Set Partitioning formulation and CG | [Fe], [TV]; | |
| Vehicle Routing: Cutting and Branching; Notes on Branching | [Wo sc 11.7 in LMS]; [C]; Assignment 1 | |
| 18 | ||
| Surrogate and Lagrangian Relaxations for MILP | ||
| Practice on Lagrangian Relaxation (Multicommodity flows) | ||
| 19 | Lagrangian Relaxation and Integer Programming | |
| Applications: Vehicle Scheduling | ||
| Crew Scheduling; RCSP | ||
| 20 | Benders’ Algorithm; Version 2 | |
| Practice on Benders’ Algorithm | ||
| Stochastic Programming | ||
| 21 | Stochastic Programming; Integer Programming and Heuristics; Notes | |
| Integer Programming and Machine Learning | ||
| Formulating Equity and Fairness in Optimization Models |
[KN1] Ed Klotz, Alexandra M. Newman. Practical guidelines for solving difficult linear programs Surveys in Operations Research and Management Science, 18 (1–2) (2013), pp. 1-17
[HL] Frederick S Hillier and Gerald J Lieberman, Introduction to Operations Research, 9th edition, 2010. ISBN: 0073376299. Extracts available in [LMS].
[MG] J. Matousek and B. Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007
[NW] J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition. Springer Series in Operations Research, 2006.
[V] Robert J. Vanderbei, Linear Programming: Foundations and Extensions, Fourth Edition, Springer. 2014.
[BGLMS] Bixby, R. E., Gregory, J. W., Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1992). Very large-scale linear programming: A case study in combining interior point and simplex methods. Technical Report 91-11 (Also in Operations Research, 40(5), 885.)
[KN2] Ed Klotz Alexandra M. Newman. Practical guidelines for solving difficult mixed integer linear programs Surveys in Operations Research and Management Science Volume 18, Issues 1–2, October 2013, Pages 18-32
[ABGRW] Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger. Presolve Reductions in Mixed Integer Programming INFORMS Journal on Computing, 32(2), 2020 (preprint available as ZIB-Report 16-44)
[Wi] H.P. Williams. Model building in mathematical programming. John Wiley & Sons, Chichester, Fifth Edition, 2013
[A] David L. L. Applegate, Robert E. E. Bixby, Vasek Chvátal, William J. J. Cook. The traveling salesman problem: a computational study. 2006
[ABCC] David Applegate, Robert Bixby, Vasek Chvatal, William Cook. Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Mathematical Programming, Series B. 97. 2003
[DFJ] G. Dantzig, R. Fulkerson and S. Johnson. Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America, Vol. 2, No. 4 (Nov., 1954), pp. 393-410
[P] Gabor Pataki. Teaching Integer Programming Formulations Using the Traveling Salesman Problem SIAM Review 45(1), 2003
[MTZ] C. E. Miller, A. W. Tucker, R. A. Zemlin Integer Programming Formulation of Traveling Salesman Problems Journal of the ACM. 7(4), 1960
[OAL] Temel Öncana, I. Kuban Altınelb, Gilbert Laporte. A comparative analysis of several asymmetric traveling salesman problem formulations Computers & Operations Research 36 (2009)
[AMO] R.K. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Chapters 16 and 17. Prentice Hall, 1993
[LD] M.E. Lübbecke, J. Desrosiers Selected Topics in Column Generation. Operations Research. Vol. 53, No. 6, 2005
[Fe] Feillet, D. A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR-Q J Oper Res (2010) 8: 407.
[Wo] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 2021. Extract available from ItsLearning.
[TV] Toth P. and Vigo D. (eds) Vehicle routing: Problems, Methods and Applications, Second Edition, Society for Industrial and Applied Mathematics, 2014
Ordinary exam: two assignments during the course
Reexam: assignments in August 2024