Schedule
... see timetable
You can import the schedule in your calendar using the iCalendar file at
this URL
Lecture Program
| Lec. | Topic and Slides | Literature |
|---|
| 1 | apr8 | Introduction - Linear Programming, Notation | |
| | Resource allocation in factory planning. Diet problem. | [L1] [HL ch 1,2,3] |
| | Linear programming problems and geometrical interpretation. | [MG ch 1,2, Appendix] [L2] |
| | History. Fourier & Moutzkin elimination | [Da] [ wiki ] |
| 2 | apr9 | Linear Programming, Simplex Method | |
| | Notation: polyhedral analysis | [MG ch 4] [HL sc 5.1] [L3] |
| | Linear programming theory, Fundamental theorem | [L4] |
| | Gaussian Elimination | [ wiki ] [L2] |
| | Simplex method | [MG ch 5] [HL sc 4.1-4.4] |
| 3 | apr22 | Simplex Method and Exception Handling | |
| | Simplex method, tableaux and dictionaries | |
| | Exception handling and degeneracies in simplex method. Pivot rules | [MG ch 5], [HL sc 4.5] |
| 4 | apr24 | Initialization and Duality | |
| | Initialization | [Va sc 2.3] [HL sc 4.6] |
| | Duality: bounding and multipliers approach | [HL sc 6.1-6.4] |
| | Weak/strong duality theorems and complementary slackness theorem | [MG sc 6.1-6.3] [Ch ch 5 (BB)] |
| 5 | apr29 | Dual Simplex, Duality by Lagrangian relaxation | |
| | Duality by Lagrangian multipliers | [CL sc 2] |
| | Dual Simplex. Economic interpretation | [Va ch 5] [ Assignment 1 ] |
| 6 | may6 | Geometric Interpretation, Sensitivity Analysis and Farkas Lemma | |
| | Geometric interpretation | [Ch ch 17 (BB)] |
| | Sensitivity analysis, examples. | [Ch ch 10 (BB)] [Va sc 7.1] [HL sc 4.5] |
| | Farkas Lemma | [MG sc 6.4] [An] |
| 7 | may7 | Revised Simplex Method | |
| | Farkas Lemma and infeasibility certificates | [An] |
| | Revised Simplex Method and Efficiency Issues | [Ch ch 7 (BB)] [Va sc 4.1-4.3, 8.1] [L5] |
| 8 | may13 | Integer Programming - Modeling Examples | |
| | ILP Modeling, Covering, Knapsack, Assignments, Matchings, Graph Problems | [ch 3 of MG] |
| 9 | may14 | Integer Programming - More on Modeling, Formulations, Relaxations | |
| | Disjunction constraints, Uncapacitated facility location problem, TSP | [Wo ch 1 (BB)] |
| | Relaxations, Primal and dual bounds, | [Wo ch 2 (BB)] |
| | Properties of easy problems. | [Wo sc 3.1 (BB)] |
| 10 | may20 | Well Solved Problems, Network Flows | [ Assignment 2 ] |
| | Convex hull description, Total unimodular matrices, | [Wo sec. 3.2-3.5 (BB)] |
| | Network flows, Maximum flow, Min cost flow | [CL ch 7] |
| 11 | may21 | More on Network Flows | |
| | Network flows problems, models, algorithms and examples | [Wo sc 3.5] |
| | Duality of Network Flow problems and Network Simplex | [CL ch 7] |
| | ILP in Excel | [L7] [L8] [L9] mincost.xlsx |
| 12 | may27 | Cutting Planes - Branch and Bound | |
| | Valid Inequalities, Formulations, strength, inequalities. Chvatal Gomory cuts. | [Wo ch 8.1-8.6 (BB)] |
| | Cutting plane algorithm. Gomory's fractional cutting plane algorithm, example. | [L10] |
| | Branch and Bound, example | [Wo ch 7 (BB)] |
| 13 | may28 | More on Modelling and Preprocessing | |
| | Preprocessing, set covering preprocessing | |
| | Modelling tricks in IP, nonlinear programs, piecewise functions | [Wi ch 9 (BB)] |
Exercises
The exercise sessions are held by: Christian Nørskov. Some material can
be found at his DM545 page
| Sess. | Topic | Exercises |
|---|
| 1 | apr11 | Modelling in LP and the Simplex Method | Sheet 1 |
| 2 | apr23 | LP Software (note: in IMADA Terminal room!) | Sheet 2 |
| 3 | apr30 | Duality | Sheet 3 |
| 4 | may9 | Sensitivity Analysis and Revised Method | Sheet 4 |
| 5 | may14 | LP recap. + IP Modeling | Sheet 5 |
| 6 | may23 | IP Modeling | Sheet 6 |
| 7 | may27 | Network flows | Sheet 7 |
| 8 | may30 | Cutting Planes and Branch and Bound | Sheet 8 |
| 9 | jun4 | Question Time | Sheet 9 Sol |
| 10 | jun6 | Rehearsal | |
Literature
Main sources
- [MG] J. Matousek and B. Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007
- [Wo] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 1998
- [FGK] Robert Fourer, David M. Gay, and Brian W. Kernighan, AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Brooks
Cole, Publishing Company, 2003. A shorter article: R. Fourer, D.M. Gay
and B.W. Kernighan. A Modeling Language for Mathematical Programming. Management Science, INFORMS, 1990, 36(5), pp. 519-554
(http://www.ampl.com/REFS/amplmod.pdf)
Software and Data
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:
Alternatively, it is possible to work with Python (and of course also
with C, C++ and Java)
Assessment
- Two obligatory assignments. Internal examiner by
teacher. Pass/fail. The assignments are practice oriented and must be
passed to attend the written exam.
- Written exam on June 10, 4 hours from 9:00 to 14:00 in U9 and U27,
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.
- [Hint: being acquainted with the following tools (or their equivalent
in your system) would help you to write your solutions better and faster:
- Mathematical formulas, if not handwritten, are best encoded in
LaTeX (avoid Word and similar)
- text editor in VERBATIM mode (Unix: EMACS + ORG mode; Win: Gusek)
- AMPL
- R, MATLAB, Maple, python (see package "numpy" for matrix operations
and package "fractions")
- grapher in Mac to plot graphs
- calculator for basic math operations
- tikz for drawing networks.
- Danish Dictionary
- Latex symbol classifier]
Course Evaluation by Students
Date: 2014-12-11T17:07+0100
Author: marco
Org version 7.9.3f with Emacs version 24
Validate XHTML 1.0
|