DM559/DM545 -- Linear and Integer Programming
Schedule
DM559
View Section H1.
Section H2 (cancelled by Monday of week 14. Go to H1 or M1).
DM545
View Section M1.
Classes (introduction + exercises)
Linear Algebra Part
| |
Date |
Topic and Slides |
Literature and Assignments |
| I1 |
31.01 |
Introduction. Preliminaries |
[AH pp 1-8] |
| I2 |
01.02 |
Matrices and Vectors |
[AR s 1.3-1.4] or [AH s 1.1-1.9] or [Le s 1.3-1.4] |
| E1 |
01.02 |
Matrix operations |
Sheet 1; sol |
| I3 |
08.02 |
Geometric Insight |
[AR s 3.1-3.4] or [AH s 1.9-1.14] |
| E2 |
07.02 |
Computer Lab: Python and Linear Algebra. Tutorial. Networkx. |
Sheet 2; sol |
| E3 |
10.02 |
Geometric Interpretation |
Sheet 3; sol |
| I4 |
15.02 |
Systems of Linear Equations |
[AR s 1.1-1.2] or [AH c 2] or [Le s 1.1-1.2, 1.5] |
| E4 |
15.02 |
Linear Systems |
Sheet 4; sol |
| E5 |
16.02 |
Linear Systems |
Sheet 5; sol |
| I5 |
21.02 |
Elementary Matrices, Determinants, Matrix Inverse |
[AR s 1.4-1.7, c 2] or [AH c 3] or [Le s 1.5, 2.1-2.3] |
| I6 |
22.02 |
Rank, Range and Vector Spaces.
Numerical methods (LU + iterative) |
[AR s 4.1-4.2, 9.1] or [AH c 4] or [Le s 3.1,3.2,3.6] |
| E6 |
22.02 |
Determinants, Matrix Inverse |
Sheet 6 sol |
| I7 |
28.02 |
Linear Independency, Bases, Dimensions |
[AR s 4.3-4.5] or [AH c 5,6] or [Le s 3.3,3.4,3.6] |
| I8 |
01.03 |
Linear Transformations, Change of Basis |
[AR 4.6,4.9-4.10, 8.1,8.3,8.4] or [AH c7] or [Le 4.1,4.2,3.5]
[Assignment 0.1; sol] |
| E7 |
01.03 |
Applications |
|
| E8 |
07.03 |
Vector spaces, bases, change of basis, linear transformations |
Sheet 8; sol |
| E9 |
08.03 |
Computer Lab. More on arrays in Python. Sparse Matrices |
Sheet 9; sol |
| E10 |
09.03 |
|
|
| I9 |
15.03 |
Eigenvalues and Eigenvectors |
[AR c 5.1,5.2] or [AH c 8,9] or [Le s 4.3, s 6.1,6.3]
[Assignment 0.2; sol] |
| E11 |
15.03 |
Eigenvalues, Eigenvectors, Diagonalization |
Sheet 11; sol |
Linear and Integer Programming Part
| |
Date |
Topic and Slides |
Literature and Assignments |
| E0 |
w11 |
Python and Linear Algebra Review (only for DM545) |
Assignment 1.0; sol |
| I1 |
mar22 |
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] |
| I2 |
mar24 |
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] |
| E1 |
w12 |
LP Modeling |
Sheet 1; sol |
| I3 |
mar29 |
Simplex Method [Slides] |
[ Notes ] |
| |
|
Simplex method, tableaux and dictionaries |
[MG ch 5] [HL sc 4.1-4.4] |
| E2 |
w13 |
Simplex |
Sheet 3; sol |
| E3 |
w13 |
LP Software (note: in IMADA Computer Lab!) |
Sheet 2; |
| I4 |
apr5 |
Exception Handling and Initialization [Slides] |
[ Notes ] |
| |
|
Exception handling and degeneracies in simplex method. Pivot rules |
[MG ch 5], [HL sc 4.5] |
| I5 |
apr7 |
Duality [Slides] |
[ Notes ] |
| |
|
Duality: bounding and multipliers approach |
[HL sc 6.1-6.4] |
| |
|
Weak/strong duality theorems and complementary slackness theorem |
[MG sc 6.1-6.3] |
| |
|
|
[Assignment 1.1; sol ] |
| E4 |
w14 |
Exception Handling |
Sheet 4; sol |
| I6 |
apr19 |
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] |
| I7 |
apr21 |
Revised Simplex Method [Slides] |
[ Notes ] |
| |
|
|
[HL ch 5] [Va 6.1-6.5] |
| |
|
|
[ Ch ch 7 ] |
| E5 |
w16 |
Duality |
Sheet 5; sol |
| 8 |
apr26 |
Integer Programming - Modeling Examples [Slides] |
[MG ch 3] [Wo ch 1] |
| E6 |
w17 |
Lab session (note: in IMADA Computer Lab!)
Sensitivity Analysis and Revised Method |
Sheet 6; sol |
| E7 |
w17 |
IP Modeling |
Sheet 7; sol |
| I9 |
may2 |
Integer Programming - More on Modeling, Formulations [Slides] |
[Wi ch 9.1-9.5] [Wo ch 2] [L8] |
| I10 |
may3 |
Relaxations, Well Solved Problems [Slides] |
[Wo sec. 3.2-3.5] [CL ch 7] |
| |
|
Convex hull description, Total unimodular matrices |
|
| I11 |
may9 |
Network Flows [Slides] |
[CL ch 4,6,7] |
| I12 |
may10 |
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 ] |
| E8 |
w18 |
More on IP modeling |
Sheet 8; sol |
| I13 |
may17 |
Cutting Planes + Branch and Bound [Slides] |
[Wo ch 7, 8.1-8.6] |
| |
|
Valid Inequalities. Chvatal Gomory cuts. |
[Wo ch 7] |
| |
|
Cutting plane algorithm. Gomory's fractional cutting plane algorithm |
|
| |
|
Branching strategies |
|
| I14 |
may19 |
Branch and Bound + Traveling Salesman Problem |
|
| E9 |
w19 |
Yet more on IP modeling + well solved problems |
Sheet 9; sol |
| E10 |
w20 |
Network flows |
Sheet 10; sol |
| E11 |
w21 |
Cutting Planes and Branch and Bound |
Sheet 11; sol |
| E12 |
w21 |
Exam rehearsal |
Sheet 12; sol |
Literature
Linear Algebra Part:
- Recommended books:
- 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
Python:
Web applications on the simplex
MILP in spread sheets
- Links
Assessment
- A number of obligatory assignments during the course with pass/fail
assessment by the teacher. The assignments are practice oriented and
must be passed to attend the written exam.
- Written exam, 4 hours, Danish 7 grade scale, external
examiner
- Instructions for the written exam
- The written exam is scheduled for the 13th of June from 10:00 to 14:00
in U151, U152, U153.
- Reexam: 16th of August (written). Admission is allowed to only those
who have passed the obligatory assignment.
Course Evaluation
Midway evaluation:
Final evaluation:
|