Teacher: Marco Chiarandini
Instructor: Peter Bjørn
| Week | Topics | Resources | Activities |
|---|---|---|---|
| E | Exercises: Linear Algebra Review | Sheet 0; Solutions | |
| 5 L | Course Organization | Slides; LN pp 1-7 | |
| Introductory elements: Linear Programming, Notation | |||
| Resource allocation in factory planning. | [HL ch 1,2,3] | ||
| Linear programming problems and geometrical interpretation. | [MG ch 1,2, Appendix] | ||
| L | Diet problem | Slides; LN pp 7-21 | |
| Fourier & Moutzkin elimination | [Da] wiki | ||
| Notation: polyhedral analysis | [F ch 1, 2]; [MG ch 4]; [HL sc 5.1] | ||
| E | Exercises: LP Modeling | Sheet 1; Solutions | |
| 6 L | Simplex Method | Slides; LN | |
| Geometry and Algebra of Linear programming theory, Fundamental theorem | wiki | ||
| Gaussian Elimination | [F pp 33-48]; [MG ch 5]; [HL sc 4.1-4.4] | ||
| Simplex method, tableaux and dictionaries | [Python T2] | ||
| L | Exception Handling, degeneracies, pivot rules, | Slides; LN; Compedium | |
| Initialization | [F pp 48-58]; [MG ch 5]; [HL sc 4.5]; [TR] | ||
| E | Exercises: Simplex Method | Sheet 2; Solutions (Marco); Solutions (Joannes) | |
| 7 L | Duality Derivation: | Slides; LN; [F sec 5.1-5.5] | |
| Bounding and multipliers approach | [MG sc 6.1-6.3]; [HL sc 6.1-6.4] | ||
| Duality Theory: | |||
| Weak/strong duality theorems and complementary slackness theorem | |||
| L | Duality Applications: Dual Simplex, Sensitivity Analysis | Slides; LN; [F sec 5.6-5.8]; [Va sc 7.1]; [CL ch 2] | |
| E | Exercises: Duality | Sheet 3; Solutions | |
| 8 L | Sensitivity Analysis | [HL sc 7.1, 4.7] | Tuesday, |
| Revised Simplex Method | Slides; LN; [F, sec 4.3]; [Ch ch 7]; [HL ch 5]; [Va 6.1-6.5] | Test 1 | |
| L | Integer Programming - Overview | Slides; LN; [F, ch 2, sc 6.1] | |
| Modeling examples | |||
| E | Sensitivity Analysis, Revised Simplex Method | Sheet 4; Solutions | |
| 9 L | More Modeling Examples | Slides; [LN sc 5.2, 5.3]; [MG sc 6.4, 6.6, ch 3]; [Wo ch 1]; [Wi ch 9.1-9.5] | |
| L | Formulations, Relaxations | Slides; [LN sc 5.4, 6]; [Wo ch 2] | |
| E | IP Modeling | Sheet 5; Solutions | |
| 10 L | Chvatal Gomory cuts. Cutting Plane Algorithms | Slides | Tuesday, |
| [LN ch 8]; [Wo ch 8.1-8.6]; [F sc 6.3] | Test 2 | ||
| L | Branch and Bound | Slides; [LN ch 9]; [Wo ch 7]; [F sc 6.4]; [GRB] | |
| E | Cutting Planes and Branch & Bound | Sheet 6; Solutions | |
| 11 L | Well Solved Problems: Total unimodular matrices; Network Flows | Slides [F sc 6.2]; [Wo sec. 3.2-3.5] | |
| L | Network Flows: Applications; Duality in Network Flows | Slides; [AMO-ch1]; [Wi-ch9] | |
| E | Total Unimodular Matrices and Network Flows | Sheet 7; Solutions | |
| 12 L | Network Simplex; Farkas Lemma | Slides; [CL pp 7.1-7.2]; [AMO pp 11.1-11.5]; [F pp 67-68] | |
| L | Practice Workshop with ILP Software: Application Case | Unit Commitment (Sol); Factory Planning and Maintenance (Sol) | |
| E | Modeling with Network Flows | Sheet 8; Solutions | |
| 13 | Tuesday, | ||
| Test 3 |
[F] M. Fischetti, Introduction to Mathematical Optimization Independently published, 2019
[MG] J. Matousek and B. Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007
[Wo] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 1998.
[LN] M. Chiarandini. Lecture Notes. 2021.
[Wi] H.P. Williams. Model building in mathematical programming. John Wiley & Sons, Chichester, Fifth Edition, 2013
[HL] Frederick S Hillier and Gerald J Lieberman, Introduction to Operations Research, 9th edition, 2010. ISBN: 0073376299
[Ch] V. Chvatal. Linear Programming. W.H.Freeman, 1983
[Va] R. Vanderbei. Linear Programming: Foundations and Extensions. Springer US, 2008
[Da] G.B. Dantzig. Linear Programming. Operations Research, 2002, 50(1), 42-47
[AMO] R.K. Ahuja, T.L. Magnanti and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993
[TR] Tim Roughgarden. Beyond Worst-Case Analysis. Communications of the ACM, March 2019, Vol. 62 No. 3, Pages 88-96.
[CL] J. Clausen and J. Larsen. Supplementary notes to networks and integer programming. Lecture Notes, DTU, 2009
General tutorials from slides in DM561:
[T1] Tutorial on Jupyter (aka IPython) notebooks, numpy and Linear Algebra
[GRB] Solving MILP Problems in Python with Gurobi: Part 1; Part 2
Tools for plotting graphs: LP Grapher, grapher in Mac, graph.tk.
[WC] Stefan Waner and Steven R. Costenoble. Simplex Method tool
[NS] NEOS server
Reexam: Oral in August