DM559/DM545 -- Linear and Integer Programming
Links
- Teacher: Marco Chiarandini
- Instructor H1: Lasse Malm Lideggard
- Instructor O1: Anna Bomersbach
Schedule
View DM559 Section H1.
View DM545 Section O1.
Another view is available from MitSDU. Import the calendar feed from
there. (Note that Section H2 has been cancelled.)
Introductory Classes
Linear Algebra Part
| |
Date |
Topic and Slides |
Literature and Assignments |
| 1 |
01.02 |
Introduction. Preliminaries |
[AH pp 1-8] |
| 2 |
03.02 |
Matrices and Vectors |
[AH s 1.1-1.9] or [Le s 1.3-1.4] or [AR s 1.3] |
| 3 |
08.02 |
Geometric Insight |
[AH s 1.9-1.14] or [AR s 3.1-3.4] |
| 4 |
12.02 |
Systems of Linear Equations |
[AH c 2] or [Le s 1.1-1.2, 1.5] or [AR s 1.1-1.2] |
| 5 |
17.02 |
Elementary Matrices, Determinants, Matrix Inverse |
[AH c 3] or [Le s 1.5, 2.1-2.3] or [AR s 1.4-1.7, c 2] |
| 6 |
04.03 |
Rank, Range and Vector Spaces |
[AH c 4] or [Le s 3.1,3.2,3.6] or [AR s 4.1-4.3,4.7-4.8] |
| 7a |
04.03 |
Vector Spaces, Linear Independency, Bases, Dimensions |
[AH c 5,6] or [Le s 3.3,3.4,3.6] |
| 7b |
10.03 |
Vector Spaces, Linear Independency, Bases, Dimensions |
[AH c 5,6] or [Le s 3.3,3.4,3.6] |
| 8 |
11.03 |
Linear Transformations |
[AH c 7] or [Le 4.1,4.2,3.5] |
| 9 |
11.03 |
Diagonalisation |
[AH c 8,9] or [Le s 4.3, s 6.1,6.3] [ Obligatory Assignment 0 ] [ sol ] |
Linear and Integer Programming Part
| |
Date |
Topic and Slides |
Literature and Assignments |
| 1 |
04.04 |
Introduction - Linear Programming, Notation |
[ 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 |
06.04 |
Linear Programming, towards the Simplex Method |
[ 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 |
11.04 |
Simplex Method |
[ Notes ] |
| |
|
Simplex method, tableaux and dictionaries |
[MG ch 5] [HL sc 4.1-4.4] |
| 4 |
18.04 |
Exception Handling and Initialization |
[ Notes ] |
| |
|
Exception handling and degeneracies in simplex method. Pivot rules |
[MG ch 5], [HL sc 4.5] |
| 5 |
19.04 |
Duality |
[ 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] [ Obligatory Assignment 1 ] [ sol, cmnts ] |
| 6 |
25.04 |
More on Duality |
[ 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 |
27.04 |
Revised Simplex Method |
[ Notes ] |
| |
|
|
[HL ch 5] [Va 6.1-6.5] |
| |
|
|
[ Ch ch 7 ] |
| 8 |
02.05 |
Integer Programming - Modeling Examples |
[MG ch 3] [Wo ch 1] |
| 9 |
09.05 |
Integer Programming - More on Modeling, Formulations |
[Wi ch 9.1-9.5] [Wo ch 2] [L8] |
| 10 |
11.05 |
Relaxations, Well Solved Problems |
[Wo sec. 3.2-3.5 (BB)] [CL ch 7] |
| |
|
Convex hull description, Total unimodular matrices |
|
| 11 |
18.05 |
Network Flows |
[CL ch 4,6,7] [ Obligatory Assignment 2 ] [ sol ] |
| |
|
Min cost flow, Maximum flow, Shortest path, multicommodity flow |
|
| |
|
Duality in network flows |
|
| 12 |
20.05 |
Cutting Planes - Branch and Bound |
[ Notes ] |
| |
|
Valid Inequalities. Chvatal Gomory cuts. |
[Wo ch 7, 8.1-8.6 (BB)] |
| |
|
Cutting plane algorithm. Gomory's fractional cutting plane algorithm |
|
| |
|
Branch and Bound, examples |
|
| 13 |
23.05 |
More on Branch and Bound (slides from previous lecture) |
|
| |
|
Branching strategies, Assignment and Transportation Problems |
[Wo ch 7 (BB)] [AOM sec 1.2 (BB)] |
| |
|
Modeling |
[Wi, ch 9 (BB)] |
| 14 |
26.05 |
Lab on Assignment 2 |
|
Exercises
Linear and Integer Programming Part
Literature
Linear Algebra Part:
- Recommended books:
- Other References:
- [AR] Howard Anton and Chris Rorres. Elementary Linear Algebra. 11th
Edition. 2015. Wiley
- 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
- [Va] R. Vanderbei. Linear Programming: Foundations and Extensions. Springer US, 2008
- [Wi] H.P. Williams. Model building in mathematical programming. John Wiley & Sons, Chichester, Fifth Edition, 2013
- [Da] G.B. Dantzig. Linear Programming. Operations Research, 2002, 50(1), 42-47
- [CL] J. Clausen and J. Larsen. Supplementary notes to networks and integer programming. Lecture Notes, DTU, 2009
- Tools
Python:
Web applications on the simplex
MILP in spread sheets
- Links
- Similar courses:
Assessment
- Three/Two obligatory assignments 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
- Reexam: 18th-19th August. (You do not need the obligatory assignments
if you have already passed them during the course):
|