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; Sol |
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]; Sheet 5; Assignment 1 | |
18 | Surrogate and Lagrangian Relaxations for MILP | [Wo ch 10 in LMS]; [Fi] |
Practice on Lagrangian Relaxation | Sheet 6; Sol [AMO ch 16 + 17.4 in LMS] | |
Further Notes on Lagrangian Relaxation | ([IB]; [JB]; [Fi2]); [Fi, sc 8]; [AMO sc 16.4-16.5]; [Wo ch 10 in LMS] | |
19 | Applications: Vehicle Scheduling | [BCG]; [CG] |
Crew Scheduling; RCSP | [SGSK]; [GM]; Sheet 7 | |
Integer Programming and Heuristics | [Wo ch 13]; [FL] | |
20 | Stochastic Programming | [B]; [Wo p 241]; [SP] |
Formulating Equity and Fairness in Optimization Models | [CH] | |
Practice on Stochastic Programming | Sheet 8; sol in [LMS] under Resources | |
21 | Multiobjective optimization | [TV], [E] Assignment 2 |
Further Topics out of curriculum
Benders’ Algorithm; Version 2 | [Wo ch 12 in LMS]; [DJ]; [Z]; | |
Practice on Benders’ Algorithm | Sheet 9; Sol; Sol1; Sol2 | |
Integer Programming and Machine Learning | [Wo sc 14.6 in LMS]; [BD]; [FJ] |
[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
[E] Matthias Ehrgott. (2005) Multicriteria Optimization, Second Edition. Springer Berlin.
[Fi] M.L. Fisher. The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 2004, 50(12), 1861-1871
[Fi2] M.L. Fisher. An applications oriented guide to Lagrangian relaxation Interfaces 15:2, 10-21, 1985.
[IB] S. Ilker Birbil. Lagrangian Relaxation. 2016
[JB] J. E. Beasley. Integer Programming Solution Methods.
[BCG] A.A. Bertossi, P. Carraresi and G. Gallo. On some matching problems arising in vehicle scheduling models. Networks, Wiley, 1987, 17(3), 271-281
[CG] P. Carraresi and G. Gallo. Network models for vehicle and crew scheduling. European Journal of Operational Research , 1984, 16(2) , 139 - 151
[SGSK] I. Steinzen, V. Gintner, L. Suhl and N. Kliewer. A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots. Transportation Science, 2010, 44(3), 367-382
[GM] S. Gualandi and F. Malucelli. Resource Constrained Shortest Paths with a Super Additive Objective Function. M. Milano (ed.). CP, Springer, 2012, 7514, 299-315
[FL] M. Fischetti, A. Lodi, Heuristics in Mixed Integer Programming, Wiley Encyclopedia of Operations Research and Management Science (James J. Cochran ed.), John Wiley & Sons, Vol. 8, 738-747, 2011.
[B] John E Beasley Stochastic Programming in OR-Notes
[CH] Violet (Xinying) Chen and J. N. Hooker. A Guide to Formulating Equity and Fairness in an Optimization Model. Video
[TV] Satya Tamby, Daniel Vanderpooten. (2021) Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems. INFORMS Journal on Computing 33(1):72-85
[DJ] Dirickx YMI & Jennergren LP (1979). Systems Analysis by Multilevel Methods: With Applications to Economics and Management. Chichester, UK: John Wiley & Sons. ISBN 978-0-471-27626-5
[Z] Zhang, Ray Jian, Benders Decomposition: An Easy Example. 2016. Video
[BD] Bertsimas, D. and Dunn, J. (2017). Optimal classification trees. Machine Learning 106(7): 1039–1082.
[BD2] Bertsimas, D. and Dunn, J. (2019). Machine Learning Under a Moden Optimization Lens. Dynamic Ideas LLC.
[FJ] Fischetti, M. and Jo, J. (2018). Deep neural networks and mixed integer linear optimization. Constraints 23: 296–309.
Ordinary exam: two assignments during the course
Reexam: assignments in August 2024