DM545/DM871 -- Linear and Integer Programming

Links

Schedule

DM545 (mitSDU), DM871 (mitSDU) (The two courses and sections H1 and M1 have exactly the same schedule)

DM545 M1, weekly view
Week678910111213
Man 14-16f
(U32)		f
(U166)		f
(U166)		f
(U153)		f
(U155)		f
(U166)		f
(U166)		f
(U153)
Ons 8-10f
(U166)
Ons 12-14f
(U156)		f
(U166)		f
(U9)		f
(U155)		f
(U153)		f
(U166)
Tor 8-10f
(ComputerLab)		m1e
(U163)		m1l
(ComputerLab)		m1e
(U50A)		m1e
(U50A)		m1e
(U166)		m1e
(U154)		m1e
(U153)
Fre 8-10f
(ComputerLab)
DM871 H1, weekly view
Week678910111213
Man 14-16f
(U32)		f
(U166)		f
(U166)		f
(U153)		f
(U155)		f
(U166)		f
(U166)		f
(U153)
Ons 8-10f
(U166)
Ons 12-14f
(U156)		f
(U166)		f
(U9)		f
(U155)		f
(U153)		f
(U166)
Tor 8-10h1e
(U32)		h1e
(U163)		h1e
(ComputerLab)		h1e
(U50A)		h1e
(U50A)		h1e
(U166)		h1e
(U154)		h1e
(U153)
Fre 8-10f
(ComputerLab)

Contents

Introductory classes

Week # Topics Literature Slides Test
6 1 Introduction - Linear Programming, Notation [ Notes ] lec1  
    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 Linear Programming, towards the Simplex Method [ Notes ] lec2  
    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]    
7 3 Simplex Method [ Notes ] lec3  
    Simplex method, tableaux and dictionaries [MG ch 5] [HL sc 4.1-4.4]    
  4 Exception Handling and Initialization [ Notes ] lec4  
    Exception handling and degeneracies in simplex method. Pivot rules [MG ch 5], [HL sc 4.5] compedium Test 1
8 5 Duality Derivation: [ Notes ] lec5  
    Bounding and multipliers approach [MG sc 6.1-6.3] [HL sc 6.1-6.4]    
  6 Duality Theory:      
    Weak/strong duality theorems and complementary slackness theorem      
9 7 More on Duality [ Notes ] lec6  
    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]    
  8 Revised Simplex Method [ Notes ]    
      [HL ch 5] [Va 6.1-6.5] lec7  
      [ Ch ch 7 ]   Test 2
10 9 Completion of previous lectures      
  10 Integer Programming - Modeling Examples, Formulations [MG sc 6.4, 6.6, ch 3] [Wo ch 1]
[Wi ch 9.1-9.5] [Wo ch 2]		 lec9  
11 11 Relaxations, Cutting Planes [Wo ch 7] lec10  
    Valid Inequalities. Chvatal Gomory cuts.      
    Cutting plane algorithm. Gomory's fractional cutting plane algorithm   gomory  
  12 Branch and Bound [Wo ch 8.1-8.6] bnb Test 3
12 13 Well Solved Problems [Wo sec. 3.2-3.5] [CL ch 7] netflows  
    Convex hull description, Total unimodular matrices      
    Network Flows [CL ch 4,6,7]    
13 13 Network Flows [ Notes ]    
    Min cost flow, Maximum flow, Shortest path, multicommodity flow [AOM sec 1.2]   Test 4

Training classes

Week # Topic Exercises Sol
6 0 Python and Linear Algebra Review Sheet0; intro to Python: part 1; part 2 Sheet0
7 1 LP Modeling Sheet1 Sheet1
8 2 Simplex Method Sheet2 Sheet2 (Johannes); Sheet2 (Marco)
9 3 Duality Sheet3 Sheet3 (Johannes); Sheet3 (Marco)
10 4 Dual Simplex and Revised Simplex Sheet4 Sheet4 (Johannes); Sheet4 (Marco)
12 5 IP Modeling, B&B and Cutting Planes Sheet5 Sheet5 (Johannes); Sheet5 (Marco)
12 5 B&B and Cutting Planes Sheet5b Sheet5b
13 6 Network Flows Sheet6 Sheet6
13 7 LP Software (in IMADA Computer Lab!) Lab (not in DM545);
MILP in SpreadSheets; MinCosEx; mincost.xlsx		  

Literature

Assessment

  • Class tests:
    • Test 0: February (only for DM559)
    • Test 1: February 25 at 14:00
    • Test 2: March 11 at 14:00
    • Test 3: March 25 at 14:00
    • Test 4: April 1 at 14:00
  • Oral reexam: June 4 and August 20.

Author: Marco Chiarandini

Created: 2019-03-28 Thu 08:31

Validate