DM515 – Introduction to linear and integer programming

Marco Chiarandini (marco@imada.sdu.dk)

Schedule

Week	15	16	17	18	19	20	21
Tue 10-12 (U49)	Lecture apr13	Lecture apr20	Lecture apr27	Exercise may4	Lecture may11	Lecture may18
Wed 10-12 (U49)		Exercise apr21	Exercise apr28	Lecture may5	Exercise may12	Exercise may19	Lecture may26
Thu 14-16 (U49)	Lecture apr15		Lecture apr29
Fri 10-12 (U26)		Exercise apr23 (Terminal Room)		Exercise may7 (Terminal Room)	Lecture may14	Exercise may21	Exercise may28

Lecture Content

Lec.	Topic	[Literature]
apr13	Introduction - Linear Programming, Simplex Method Short history of linear programming and diet problem. Resource allocation problem in factory planning. Linear programming problems and geometrical interpretation. Simplex method by example.	[Appendix of B1 + chp. 1, 2 and 4 of B1 + chp. 1 of B3]
apr15	Linear Programming, Simplex Method Exception handling and degeneracies in simplex method. Pivot rules. Simplex method in formal notation.	[chp. 5 of B1]
apr20	Duality Theory Tableaux and dictionaries. Duality via bounding and multipliers Weak and strong duality theorems and complementary slackness theorem Sensitivity analysis, examples. Economic interpretation.	[chp. 6.1-6.3 of B1 + chp. 2 of B3]
apr27	Integer Programming and Modelling Duality via Lagrangian relaxation. Multi-period formulation and block structure. Integer Programming. Modelling disjunction constraints, set partitioning/covering/packing, matching, 01 knapsack, traveling salesman problems	[chp. 3 of B1 + chp. 1 of B4 + sec. 9.1-9.4 of B5] [assignment1]
apr29	Integer Programming, Relaxations, Bounds and Cutting Planes Uncapacitated facility location problem. Formulations, strength, inequalities. Chvatal Gomory cuts. Cutting plane algorithm. Gomory’s fractional cutting plane algorithm, example	[chp. 8 of B4]
may5	Integer Programming - Branch and Bound Branch and bound, primal/dual bounds by LP/Lagrange/combinatorial relaxation and duality. Branch and bound components, example. Formulations for cutting stock problem.	[chp. 2 and 7 of B4, chp. 9 of B3]
may11	Well Solved Problems Properties of Easy Problems. Convex hull description and total unimodular matrices. Network flows, terminology.	[chp. 3,4, of B3 + sec. 1.4 of B6] [assignment2]
may14	Maximum Flow Network flow problems (definitions): min cost flow, shortest path, max flow, assignment, transportation, multicommodity flow, min spanning tree, matching in bipartite and arbitrary graphs. Flow decomposition. Residual network. Augmenting (s,t)-paths and max flow min cut theorem. Ford Fulkerson algorithm for max flow.	[chp. 4 of B2 or chp. 6 of B3]
may18	Min Cost Flow Push relabel algorithm for max (s,t)-flow. Minimum feasible (s,t)-flow problem, min flow max demand theorem. Optimality conditions for min cost flow, Cycle cancelling algorithm with Bellman-Ford.	[chp. 4 of B2 or chp. 7 of B3]
may26	Matchings Augmenting and alternating paths, Berge’s Theorem, Augmenting path algorithm for cardinality matching on bipartite graphs, max flow algorithm for cardinality matching on bipartite graphs, Hungarian method for weighted matching on bipartite graphs. Koenig Egervary Theorem. Hall’s Theorem.	[chp. 4 of B2 ]

Exercises

The exercise sessions are held by:

Rune Larsen (RL)
Niels H. Kjeldsen (NK)

Sess.	Topic	Exercises
apr21 (RL)	Modelling in LP and Simplex	[sheet1 html\|pdf] (updated apr15, reload page)
apr23 (NK)	LP Software, SoPlex and ZIMPL	[sheet2 html\|pdf] (ex. 3 added Apr. 21)
apr28 (RL)	Duality and Sensitivity Analysis	[sheet3 html\|pdf]
may4 (RL)	Finishing previous exercises + Modelling	[sheet4 html\|pdf] (ex. 5-7 added on May 3)
may7 (NK)	Integer Programs	[sheet5 html\|pdf]
may12 (RL)	Finishing previous exercises	[sheet6 html\|pdf]
may19 (RL)	Network problems, max flow	[sheet7 html\|pdf]
may21 (RL)	Network problems, min cost flow	[sheet8 html\|pdf]
may28 (MC)	Network flows applications	[sheet9 html\|pdf]

Literature

[B1] J. Matoušek and B. Gärtner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007

[B2] J. Bang-Jensen and G. Gutin. Flows in Networks. Chapter 4, Digraphs: Theory, Algorithms and Applications, Springer London, 2009

[B3] J. Clausen and J. Larsen. Supplementary notes to networks and integer programming. Lecture Notes, DTU, 2009

[B4] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 1998

[B5] H.P. Williams. Model building in mathematical programming. John Wiley & Sons, Chichester, 1999

[B6] A. Schrijver. Theory of Linear and Integer Programming. Wiley Interscience, 1986.

Software and Data

ZIB Optimization Suite ZIMPL, SoPlex, SCIP. ZIMPL User Guide. ZIMPL syntax highlightning for Emacs and Kate.

Assessment

Obligatory project assignments. Internal examiner by teacher. Pass/fail. The projects must be passed in order to attend the written exam.

Written exam, 4 hours. Danish 7 mark scale, external examiner. June 24, 2010.

Reexam: Oral exam, Danish 7 mark scale, external examiner. January 6, 2011. List of questions.

Past Exams

Course Evaluation