# DM545/DM871 -- Linear and Integer Programming

• DM545 (5 ECTS):
• DM871 (5 ECTS):

## 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

## 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

Created: 2020-03-26 Thu 01:14

Validate