Other material for this course is available at the associated Git repository. The drawings made during the video lectures are collected in this document.
| Week | Topics and Slides | Material |
|---|---|---|
| 14 | Introduction. Pyomo (slides). | Intro to Python; Pyomo; Sheet 1 |
| Pyomo (examples). Model Fitting (linear and non linear models). | Sheet 2; Solution S.2 | |
| Installations. Preprocessing. | [ABGRW] | |
| 16 | MILP Formulations for Traveling Salesman Problem | Sheet 3; [P] or [DFJ] or [MTZ] or [A] or [ABCC] or [OAL] |
| Cutting Planes for TSP | ||
| More on TSP. Network Flows duality | Solution S.3 | |
| 17 | Cut-and-Solve | [CZ]; Sheet 4; Solution S.4 |
| Modeling tricks | [KN1,KN2,ABGRW] | |
| Practice | ||
| 18 | Timetabling | [dW]; [LL] |
| Timetabling | Assignment 1 | |
| Practice | ||
| 19 | Lagrangian Relaxation for MILP | [AMO ch 16]; [Fi] |
| Exercises | Sheet 5; [IB]; [Fi2]; [JB] | |
| Implementation, LR for TSP | Solution S.5; [Wo ch 10] | |
| 20 | Vehicle Scheduling | [BCG]; [CG] |
| Exercises | Sheet 6 | |
| Dantzig Wolfe decomposition | [AMO ch 17]; [Wo ch 11]; [LD] | |
| 21 | Vehicle Routing: Compact models; Set Partitioning formulation and CG | [Fe] |
| Vehicle Routing: Cutting and Branching | [Fe] | |
| Exercises on Column Generation | Sheet 7 | |
| 22 | Crew Scheduling; RCSP | [SGSK]; [GM]; Assignment 2; Solution Asg 2 |
| Benders Decomposition | [DJ, sec 3.5]; Video |
[Py] Hart, William E., Carl D. Laird, Jean-Paul Watson, David L. Woodruff, Gabriel A. Hackebeil, Bethany L. Nicholson, and John D. Siirola. Pyomo – Optimization Modeling in Python. Second Edition. Vol. 67. Springer, 2017.
[ABGRW] Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger Presolve Reductions in Mixed Integer Programming INFORMS Journal on Computing, 2019 (accepted for publication, preprint available as ZIB-Report 16-44)
[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) 6
[CZ] Sharlee Climer, Weixiong Zhang. Cut-and-solve: An iterative search strategy for combinatorial optimization problems. Artificial Intelligence Volume 170, Issues 8–9, June 2006, Pages 714-738
[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
[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
[dW] D. de Werra. An introduction to timetaling. European Journal of Operational Research Volume 19, Issue 2, February 1985, Pages 151-162
[LL] G. Lach and M. Lübbecke. Optimal University Course Timetables and the Partial Transversal Polytope. C. McGeoch (ed.). 7th International Workshop on Efficient and Experimental Algorithms (WEA08), Springer, 2008, 5038() , 235-248
[AMO] R.K. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Chapters 16 and 17 (in BB). Prentice Hall, 1993
[Wo] L.A. Wolsey. Integer programming. Chapters 10 and 11 (in BB). John Wiley & Sons, New York, USA, 1998
[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
[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.
[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
[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