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]
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 [Wi ch 9.1-9.5] [Wo ch 2] [L8]
10 may3 Relaxations, Well Solved Problems [Wo sec. 3.2-3.5 (BB)] [CL ch 7]
    Convex hull description, Total unimodular matrices  
11 may9 Network Flows [CL ch 4,6,7]
    Min cost flow, Maximum flow, Shortest path, multicommodity flow  
    Duality in network flows  
12 may10 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 may17 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 may19    

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!) Sheet 6  
7 w17 Sensitivity Analysis and Revised Method Sheet 7  
8 w18 IP Modeling    
9 w19 More on IP modeling    
10 w20 Network flows    
11 w21 Cutting Planes and Branch and Bound    
12 w21 Network Flows Modeling    

Literature

Linear Algebra Part:

Linear and Integer Programming Part:

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
  • The written exam is scheduled for the 13th of June.

Past Exams

Author: Marco Chiarandini

Created: 2017-04-26 Wed 13:35

Validate