DM515 – Introduction to linear and integer programming

• Official course description at SDU
• Black Board
• Teacher: Marco Chiarandini

Week	15	16	17	18	19	20	21	22
Man, 10-12, U27A		Lecture	Lecture	Lecture	Lecture	Lecture	Lecture
Tue, 8-10, U27A	Lecture		Lecture	Lecture	Exercises	Lecture	Lecture
Thu, 14-16, U27A	Lecture	Exercises	Exercises	Exercises	Exercises		Exercises
Fri, 8-10, U26	Lecture	Exercises				Exercises	Exercises

This is a preliminary outline to be refined during the course

	Lec.	Topic	Literature	Demo and Apps
1	apr10	Introduction - Linear Programming, Notation	[Appendix of B1 + ch 1, 2 and 4 of B1]	FTLP, LP, Diet
		Diet problem. Resource allocation problem in factory planning.		Polyhedra
		Linear programming problems and geometrical interpretation.
		Notation: linear algebra, polyhedral theory.
		Fundamental theorem, Gaussian elimination.
2	apr12	Linear Programming, Simplex Method	[ch 5 of B1 or ch 2,3,4 of B8]	LP Grapher
		Examples in GnuMath. Fourier-Motzkin elimination.
		Simplex method. Tableaux and dictionaries.
3	apr13	Exception Handling and Duality Theory	[ch 5, 6.1-6.2 of B1 or ch 3,4,5 of B8]
		Exception handling and degeneracies in simplex method. Pivot rules.
		Two-phase simplex. Duality via bounding.
4	apr16	Duality Theory and Sensitivity	[ch 6.2, 6.3 of B1 + ch 5, 7.1 of B8]
		Duality via multipliers.
		Weak and strong duality theorems and complementary slackness theorem.
		Economic interpretation. Sensitivity analysis.
5	apr23	Sensitivity, Duality by Lagrangian relaxation	[ch 10 B9 (BB)]
		Sensitivity analysis, Dual Simplex, Geometric interpretation,	[p 208 B1 + sc 6.4 B1 + A1 + ch 2 B4]
		Farkas Lemma, Duality by Lagrangian multipliers
6	apr24	Revised Simplex Method. Integer Programming, Modeling, Relaxations	[ch 7 B9 (BB) + sc 1.4 B6 (BB)]
		Revised Simplex Method, Integer Programming, Modelling	[sc 1.1-1.5 B3 (BB) + ch 2,3 B1]	Simplex Method
		Uncapacitated facility location problem.
7	apr30	Integer Programming - Modeling Examples and Good Formulations	[chp. 1,2 of B3 (BB)]	Assignment 1
		Matchings, Packing, Covering, Traveling Salesman, Transportation
		Facility location, Fomulations, Primal and Dual Bounds, Relaxations
8	may1	Integer Programming - Well Solved Problems, Cutting Planes	[sc 3.1-3.3, 8.1-8.6 of B3 (BB)]
		Totally Unimodular Matrices, Chvatal-Gomory cuts
9	may7	Integer Programming - Branch and Bound	[ch 7, sc 9.6 of B3 (BB)]
		Bounding, Pruning, Branching, Preprocessing, Searching	[ch 9 of B5 (BB)]
10	may14	Network Flows, Maximum Flow	[sc 4.1-4.4 of B2]
		Networks notation, Transformations, Network flow problems: min cost flow, shortest path, max flow
		assignment, transportation, multicommodity flow, min spanning tree,
		matching in bipartite and arbitrary graphs. Flow decomposition. Residual network.
11	may15	Max Flow	[sc 4.5-4.7 of B2]	Assignment 2
		Augmenting (s,t)-paths. Max flow min cut theorem.		Max Flow 1
		Ford Fulkerson, Edmonds Karp, Push relabel algorithms for max (s,t)-flow.		Max Flow 2
12	may21	Min Cost Flow	[sc 4.8-4.10 and pp 97-99 of B2 ]	Networks Optimization
		Circulations and feasible flow. Min-flow max-demand theorem (optimality conditions).
		Minimum value feasible (s,t)-flow. Min cost flows (optimality conditions).
		Cycle cancelling algorithm with Bellman-Ford-Moore.
13	may22	Matching	[sc 8.2 of B1 and 4.10.3-4.11.2 of B2]	Max Matching
		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.

The exercise sessions are held by: Philipp Peters

	Sess.	Topic	Exercises
1	apr19	The Simplex Method and Modelling	Sheet 1
2	apr20 (in IMADA terminal room)	LP Software	Sheet 2
3	apr26	Modeling in LP, Duality, Sensitivity Analysis,	Sheet 3
4	may3	IP Modeling	Sheet 4
5	may8	Integer Programs	Sheet 5
6	may10	Finishing previous exercises	Sheet 6
7	may18	Network problems, max flow	Sheet 7
8	may24	Network problems, min cost flow	Sheet 8
9	may25	Network flows applications	Sheet 9
10	jun4 (8:30-11:30, U131)	Exam Practice
11	jun12 (9:00-11:00, U133)	Question Time	Sheet 10

In the course we will use a modelling language together with a MIP solver. There are a few possibilities, we will use the first here listed:

• GNU MathProg from the GLPK package (a subset of AMPL)
• ZIMPL from the ZIBOPT suite

Alternatively it is possible to work with Python

• Python for Gurobi
• Python for CPLEX
• Python-zibopt based on ZIBOPT
• PyMathProg uses GLPK and needs PyGLPK.
• PyGLPK uses GLPK
• PuLP works with CBC, GLPK, CPLEX, Gurobi

Comparison of solvers

• Obligatory project assignments. Internal examiner by teacher. Pass/fail. The projects must be passed to attend the written exam.
• Written exam on June 15, 2012, 4 hours. Danish 7 mark scale, external examiner. The exam must be digital. To digitalize handwritten text, formulas and graphs digital pen or hand scanner are allowed. A rehearsal of the exam is scheduled for June 4th. Take vision of the regulations that will apply.

• Pensum

• Exam 2012. Solutions

• Reexam: Oral exam, Danish 7 mark scale, external examiner.
• The reexam will be oral. Here is a List of questions.

• Exam 2011. Solutions
• Exam 2010. Solutions
• Exam 2009
• Exam 2008

• Students' Evaluation
• Handling Plan