DM545/DM871 -- Linear and Integer Programming

Schedule

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

DM545 M1, weekly view
Week678910111213
Tir 8-10f
(U154)
Tir 10-12f
(U156)		f
(U48)		f
(U154)		f
(U166)		f
(U154)
Tir 12-14f
(U48)		f
(U166)
Tor 8-10f
(U155)		f
(U156)		f
(U177)		f
(U155)
Tor 10-12f
(U48)		m1e
(U156)		m1e
(U30)		f
(U177)		f
(U166)		m1e
(U48)		m1e
(U48)
Tor 12-14m1e
(U154)		m1e
(U166)		f
(U156)		m1e
(U166)
Tor 14-16m1e
(U166)
DM871 H1, weekly view
Week678910111213
Tir 8-10f
(U154)
Tir 10-12f
(U156)		f
(U48)		f
(U154)		f
(U166)		f
(U154)
Tir 12-14f
(U48)		f
(U166)
Tor 8-10f
(U155)		f
(U156)		f
(U177)		f
(U155)
Tor 10-12f
(U48)		h1e
(U156)		h1e
(U30)		f
(U177)		f
(U166)		h1e
(U48)		h1e
(U48)
Tor 12-14h1e
(U154)		h1e
(U166)		f
(U156)		h1e
(U166)
Tor 14-16h1e
(U166)

Contents

Introductory classes

Week Topics Literature Slides Test
6 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]    
  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 Simplex Method [ Notes ] [ Python tutorial ] lec3  
  Simplex method, tableaux and dictionaries [MG ch 5] [HL sc 4.1-4.4]    
  Exception Handling and Initialization [ Notes ] [ compedium ] lec4  
  Exception handling and degeneracies in simplex method. Pivot rules [MG ch 5], [HL sc 4.5]    
8 Duality Derivation: [ Notes ] lec5  
  Bounding and multipliers approach [MG sc 6.1-6.3] [HL sc 6.1-6.4]    
  Duality Theory:      
  Weak/strong duality theorems and complementary slackness theorem      
9 More on Duality [ Notes ] lec6  
  Duality by Lagrangian relaxation [CL ch 2]    
  Dual Simplex, Sensitivity Analysis [Va sc 7.1] [HL sc 7.1, 4.7]    
  Revised Simplex Method [ Notes ] lec7  
    [HL ch 5] [Va 6.1-6.5]    
    [ Ch ch 7 ]   Test 1
10 Integer Programming - Overview [MG sc 6.4, 6.6, ch 3] [Wo ch 1]
[Wi ch 9.1-9.5]		 lec9  
  Modeling Examples, Formulations, Relaxations [Wo ch 2] lec10  
11 Relaxations, Cutting Planes [Wo ch 7] gomory  
  Valid Inequalities. Chvatal Gomory cuts.      
  Cutting plane algorithm. Gomory's fractional cutting plane algorithm [Wo ch 8.1-8.6]   Test 2
12 Branch and Bound [Wo sec. 3.2-3.5] [CL ch 7] bnb  
  Well Solved Problems   netflows  
  Convex hull description, Total unimodular matrices      
  Network Flows [CL ch 4,6,7]    
13 Network Flows: Application Examples [ Notes ] [AOM sec 1.2]    
  ILP Software MinCosEx; mincost.xlsx; MILP in SpreadSheets; Lab    
        Test 3

Training classes

Week # Topic Exercises Sol
6 0 Python and Linear Algebra Review Sheet0 without python, Sheet0 with python; intro to Python: 1; 2 Sheet00; 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)
11 5 IP Modeling Sheet5 Sheet5 (Johannes); Sheet5 (Marco)
12 6 Cutting Planes and B&B Gomory cuts; Branch and Bound gomory (Marco); bb (Marco); Nikolai
13 7 Network Flows NetFlows NetFlows

Literature

Assessment

  • 24h take home tests:
    • Test 1: week 9, Friday, February 28, from 9 to 8:59
    • Test 2: week 11, Friday, March 13, from 9 to 8:59
    • Test 3: week 14, Monday, March 30, from 9 to 8:59
  • Reexam: Oral in August

Author: Marco Chiarandini

Created: 2020-03-26 Thu 01:14

Validate