DM559/DM545 -- Linear and Integer Programming
Linear Algebra Part (DM559)
Introductory classes
| # |
Date |
Topic and Slides |
Literature and Assignments |
| 1,2 |
08.02 |
Introduction and Preliminaries. Systems of Linear Equations |
[AR s 1.1-1.2] or [AH c 2] or [Le s 1.1-1.2, 1.5] |
| 3 |
09.02 |
Matrix Operations |
[AR s 1.3-1.4] or [AH s 1.1-1.9] or [Le s 1.3-1.4] |
| 4 |
14.02 |
Elementary Matrices, Determinants, Matrix Inverse, more on Linear Systems. (LU + iterative met.) |
[AR s 1.4-1.7, c 2] or [AH c 3] or [Le s 1.5, 2.1-2.3] |
| |
15.02 |
Linear Algebra in Python. (Further elements + Sparse matrices) |
Exercises (sol) |
| 5 |
19,22.02 |
Geometric Insight |
[AR s 3.1-3.4] or [AH s 1.9-1.14]
[ Assignment 0.1 ] [ sol ] [ cmnts ] |
| 6 |
01.03 |
Rank, Range |
[AR s 4.7-4.8] or [AH c 4] or [Le s 3.1,3.2,3.6] |
| 7 |
05.03 |
Vector Spaces, Linear Independency, Bases and Dimension |
[AR s 4.1-4.5] or [AH c 5,6] or [Le s 3.3,3.4,3.6] |
| 8 |
08.03 |
Change of Basis |
[AR 4.6] or [AH c7] or [Le 4.1,4.2,3.5] |
| 9 |
12.03 |
Linear Transformations |
[AR 4.9-4.10] or [AH c 7] or [Le s 4.3] |
| 10 |
15.03 |
Diagonalization: Eigenvalues and Eigenvectors |
[AR 5.1,5.2] or [AH c 8,9] or [s 6.1,6.3]
[ Assignment 0.2 ] [ sol ] |
Linear and Integer Programming Part (DM545/DM559)
Introductory classes
| # |
Date |
Topics |
Slides |
Literature and Assignments |
| 1 |
19.03 |
Introduction - Linear Programming, Notation |
[Slides] |
[ Notes ] |
| |
|
Resource allocation in factory planning. Diet problem. |
|
[L1,L2] [HL ch 1,2,3] |
| |
|
Linear programming problems and geometrical interpretation. |
|
[MG ch 1,2, Appendix] [L3] |
| 2 |
22.03 |
Linear Programming, towards the Simplex Method |
[Slides] |
[ Notes ] |
| |
|
History. Fourier & Moutzkin elimination |
|
[Da] [ wiki ] |
| |
|
Notation: polyhedral analysis |
|
[MG ch 4] [HL sc 5.1] [L5] |
| |
|
Linear programming theory, Fundamental theorem |
|
[L4,L6] |
| |
|
Gaussian Elimination |
|
[ wiki ] [L4] |
| 3 |
04.04 |
Simplex Method |
[Slides] |
[ Notes ] |
| |
|
Simplex method, tableaux and dictionaries |
|
[MG ch 5] [HL sc 4.1-4.4] |
| 4 |
05.04 |
Exception Handling and Initialization |
[Slides] |
[ Notes ] |
| |
|
Exception handling and degeneracies in simplex method. Pivot rules |
|
[MG ch 5], [HL sc 4.5] |
| 5a |
11.04 |
Duality Derivation: |
[Slides] |
[ Notes ] |
| |
|
Bounding and multipliers approach |
|
[MG sc 6.1-6.3] [HL sc 6.1-6.4] |
| 5b |
12.04 |
Duality Theory: |
|
|
| |
|
Weak/strong duality theorems and complementary slackness theorem |
|
[ Assignment 1.1 ] [ cmts ] [ sol ] |
| 6 |
18.04 |
More on Duality |
[Slides] |
[ Notes ] |
| |
|
Geometric Interpretation, Duality by Lagrangian relaxation |
|
[Ch ch 10] [CL ch 2] |
| |
|
Dual Simplex, Sensitivity Analysis |
|
[Va sc 7.1] [HL sc 7.1, 4.7] |
| 7 |
19.04 |
Revised Simplex Method |
[Slides] |
[ Notes ] |
| |
|
|
|
[HL ch 5] [Va 6.1-6.5] |
| |
|
|
|
[ Ch ch 7 ] |
| 8 |
23.04 |
Farkas Lemma. Integer Programming - Modeling Examples |
[Slides] |
[MG sc 6.4, 6.6, ch 3] [Wo ch 1] |
| 9 |
25.04 |
Integer Programming - More on Modeling, Formulations |
[Slides] |
[Wi ch 9.1-9.5] [Wo ch 2] [L8] |
| 10 |
02.05 |
Relaxations, Well Solved Problems |
[Slides] |
[Wo sec. 3.2-3.5] [CL ch 7] |
| |
|
Convex hull description, Total unimodular matrices |
|
|
| 11 |
03.05 |
Network Flows |
[Slides] |
[CL ch 4,6,7] |
| 11b |
07.05 |
Network Flows (slides lec 11) |
|
[ Notes ] |
| |
|
Min cost flow, Maximum flow, Shortest path, multicommodity flow |
|
[AOM sec 1.2] |
| |
|
Duality in network flows |
|
[ Assignment 1.2 ] [ sol ] |
| 12 |
09.05 |
Cutting Planes |
[Slides] |
[Wo ch 7] |
| |
|
Valid Inequalities. Chvatal Gomory cuts. |
|
|
| |
|
Cutting plane algorithm. Gomory's fractional cutting plane algorithm |
|
|
| 13 |
16.05 |
Branch and Bound |
[Slides] |
[Wo ch 8.1-8.6] |
| 14 |
17.05 |
More on Modeling and MathProg in Spreadsheets |
[Slides] |
[mincost.xlsx] |
| 15 |
24.05 |
Traveling Salesman Problem |
|
[L8] [ Sol to assign. 1.2 ] |
Literature
Linear Algebra Part:
- Recommended book:
- Other References:
- Links
Linear and Integer Programming Part:
- Other References:
- [AMO] R.K. Ahuja, T.L. Magnanti and J. Orlin. Network Flows: Theory,
Algorithms, and Applications. Prentice Hall, 1993
- [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
- Tools:
- Links
|