DM559/DM545 -- Linear and Integer Programming

Schedule

DM559

View Section H1.
Week56789101112131415161718192021
Tir, 10-12I (Fælles)
(U24)
I (Fælles)
(U31)
I (Fælles)
(U31)
I (Fælles)
(U20)
I (Fælles)
(U20)
TE (H1)
(U146)
Tir, 14-16I (Fælles)
(U51)
Ons, 10-12TL (H1)
(IMADA ComputerLab)
TL (H1)
(IMADA ComputerLab)
TL (H1)
(IMADA ComputerLab)
TL (H1)
(IMADA ComputerLab)
Ons, 14-16I (Fælles)
(U20)
I (Fælles)
(U55)
I (Fælles)
(U20)
I (Fælles)
(U55)
I (Fælles)
(U55)
I (Fælles)
(U55)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
Tor, 08-10TE (H1)
(U153)
Tor, 10-12TE (H1)
(U153)
Tor, 12-14TE (H1)
(U11)
TE (H1)
(U44)
TE (H1)
(U142)
TE (H1)
(U143)
TE (H1)
(U142)
TE (H1)
(U44)
TE (H1)
(U44)
TE (H1)
(U142)
TE (H1)
(U142)
TE (H1)
(U142)
TE (H1)
(U142)
TE (H1)
(U142)
TE (H1)
(U142)
Fre, 10-12TE (H1)
(U146)
I (Fælles)
(U20)
I (Fælles)
(U48A)
I (Fælles)
(U20)
I (Fælles)
(U48A)
TE (H1)
(U10)
Section H2 (cancelled by Monday of week 14. Go to H1 or M1).

DM545

View Section M1.
Week12131415161718192021
Tir, 10-12I (Fælles)
(U20)
I (Fælles)
(U20)
Ons, 08-10TL (M1)
(IMADA ComputerLab)
TL (M1)
(IMADA ComputerLab)
TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)
Ons, 14-16I (Fælles)
(U140)
I (Fælles)
(U140)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
I (Fælles)
(U20)
Fre, 10-12I (Fælles)
(U150)
I (Fælles)
(U48A)
I (Fælles)
(U20)
I (Fælles)
(U48A)
Fre, 14-16TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)
TE (M1)
(U154)

Introductory Classes

Linear Algebra Part

  Date Topic and Slides Literature and Assignments
1 31.01 Introduction. Preliminaries [AH pp 1-8]
2 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]
3 08.02 Geometric Insight [AR s 3.1-3.4] or [AH s 1.9-1.14]
4 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]
5 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]
6 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]
7 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]
8 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]
9 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]

Linear and Integer Programming Part

  Date Topic and Slides Literature and Assignments
1 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]
2 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]
3 mar29 Simplex Method [Slides] [ Notes ]
    Simplex method, tableaux and dictionaries [MG ch 5] [HL sc 4.1-4.4]
4 apr5 Exception Handling and Initialization [Slides] [ Notes ]
    Exception handling and degeneracies in simplex method. Pivot rules [MG ch 5], [HL sc 4.5]
5 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 ]
6 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]
7 apr21 Revised Simplex Method [Slides] [ Notes ]
      [HL ch 5] [Va 6.1-6.5]
      [ Ch ch 7 ]
8 apr26 Integer Programming - Modeling Examples [Slides] [MG ch 3] [Wo ch 1]
9 may2 Integer Programming - More on Modeling, Formulations [Slides] [Wi ch 9.1-9.5] [Wo ch 2] [L8]
10 may3 Relaxations, Well Solved Problems [Slides] [Wo sec. 3.2-3.5] [CL ch 7]
    Convex hull description, Total unimodular matrices  
11 may9 Network Flows [Slides] [CL ch 4,6,7]
12 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 ]
13 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  
14 may19 Branch and Bound + Traveling Salesman Problem  

Exercises

Linear Algebra Part

  Sess. Topic Exercises Sol
1 feb01 Matrix operations Sheet 1 Sheet 1
2 feb07 Computer Lab: Python and Linear Algebra. Tutorial. Networkx. Sheet 2 Sheet 2
3 feb10 Geometric Interpretation Sheet 3 Sheet 3
4 feb15 Linear Systems Sheet 4 Sheet 4
5 feb16 Linear Systems Sheet 5 Sheet 5
6 feb22 Determinants, Matrix Inverse Sheet 6 Sheet 6
7 mar01 Applications    
8 mar07 Vector spaces, bases, change of basis, linear transformations Sheet 8 Sheet 8
9 mar08 Computer Lab. More on arrays in Python. Sparse Matrices Sheet 9 Sheet 9
10 mar09      
11 mar15 Eigenvalues, Eigenvectors, Diagonalization Sheet 11 Sheet 11

Linear and Integer Programming Part

  Sess. Topic Exercises  
0 w11 Python and Linear Algebra Review (only for DM545) Assignment 1.0 Assignment 1.0
1 w12 LP Modeling Sheet 1 Sheet 1
2 w13 LP Software (note: in IMADA Computer Lab!) Sheet 2  
3 w13 Simplex Sheet 3 Sheet 3
4 w14 Exception Handling Sheet 4 Sheet 4
5 w16 Duality Sheet 5 Sheet 5
6 w17 Lab session (note: in IMADA Computer Lab!)
Sensitivity Analysis and Revised Method
Sheet 6 Sheet 6
7 w17 IP Modeling Sheet 7 Sheet 7
8 w18 More on IP modeling Sheet 8 Sheet 8
9 w19 Yet more on IP modeling + well solved problems Sheet 9 Sheet 9
10 w20 Network flows Sheet 10 Sheet 10
11 w21 Cutting Planes and Branch and Bound Sheet 11 Sheet 11
12 w21 Exam rehearsal Sheet 12 Sheet 12

Literature

Linear Algebra Part:

Linear and Integer Programming Part:

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.

Past Exams

Author: Marco Chiarandini

Created: 2017-07-05 Wed 17:56

Validate