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
DM871 H1, weekly view
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.14.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.16.3] [HL sc 6.16.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.16.5] 




[ Ch ch 7 ] 

Test 1 
10 
Integer Programming  Overview 
[MG sc 6.4, 6.6, ch 3] [Wo ch 1] [Wi ch 9.19.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.18.6] 

Test 2 
12 
Branch and Bound 
[Wo sec. 3.23.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 
Literature
 Other References:
 [AMO] R.K. Ahuja, T.L. Magnanti and J. Orlin. Network Flows: Theory,
Algorithms, and Applications. Prentice Hall, 1993
 Tools:
 Python:
 Web applications on the simplex
 Links
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
Author: Marco Chiarandini
Created: 20200326 Thu 01:14
Validate
