Teacher: Marco Chiarandini
Instructor: Frederik Lund Andersen, Juraj Marcibál
| Week | Topics | Resources | Tests |
|---|---|---|---|
| E | Exercises: Linear Algebra Review | Sheet 0; Solutions; [T0]; [T1]; [T2]; [T3] | |
| 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]; [FM] | ||
| 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; Notebook | |
| 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 and complementary slackness theorems | |||
| 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] | |
| Revised Simplex Method | Slides; LN; [F, sec 4.3]; [Ch ch 7]; [HL ch 5]; [Va 6.1-6.5] | ||
| 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 | [LN sc 5.2, 5.3]; [MG sc 6.4, 6.6, ch 3]; [Wo ch 1]; [Wi ch 9.1-9.5] | Test 1 |
| 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; [LN ch 6]; [Wo ch 8.1-8.6]; [F sc 6.3] | |
| L | Branch and Bound | Slides; [LN ch 7]; [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 | Practice Workshop with ILP Software: Application Case | [SS]; [GRB: Part 1, Part 2] | |
| L | Finishing duality in Network flows | slides from previous week | |
| E | Modeling with Network Flows | Sheet 8; Solutions; Factory Planning and Maintenance; (Sol); Unit Commitment; (Sol); [GRB2] | |
| 14 | Test 2 | ||
[F] M. Fischetti, Introduction to Mathematical Optimization Independently published, 2019
[Wo] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 2021
[LN] M. Chiarandini. Lecture Notes. 2022.
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Chapter 29. Fourth edition, 2009, The MIT Press
[MG] J. Matousek and B. Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007
[Da] G.B. Dantzig. Linear Programming. Operations Research, 2002, 50(1), 42-47
[FM] Fourier, Moutzkin. Wikipedia entry
[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
[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
Tools for plotting graphs: LP Grapher, grapher in Mac, graph.tk.
[WC] Stefan Waner and Steven R. Costenoble. Simplex Method tool
[NS] NEOS server
Ordinary exam: two, 24h, take-home tests
Reexam: two days take-home exam in August.