Schedule
You can import the schedule in your calendar using the iCalendar file at
this URL
Lecture Program
This is a preliminary outline to be refined during the course
| Lec. | Topic and Slides | Literature |
|---|
| 1 | apr9 | Introduction - Linear Programming, Notation | |
| | Diet problem. Resource allocation in factory planning. | [L1; ch 1 of B1] |
| | Linear programming problems and geometrical interpretation. | [ch 1, 2 of B3; L3] |
| | Fourier & Moutzkin elimination | [ wiki ] |
| | Notation: linear algebra, polyhedral theory. | [Appendix of B3] |
| 2 | apr11 | Linear Programming, Simplex Method | |
| | Linear programming theory, Polyhedra | [ch 4 of B3; L7] |
| | Fundamental theorem, Gaussian elimination | [ wiki, B6, L2 ] |
| | Simplex method, Tableaux and dictionaries | [sc 2.1,2.2 of B1; ch 5 of B3] |
| 3 | apr16 | Simplex Method and Exception Handling | |
| | Exception handling and degeneracies in simplex method. Pivot rules | [ch 2,3,4 of B1; ch3 of B3] |
| | Two-phase simplex | |
| 4 | apr18 | Duality Theory and Dual Simplex | |
| | Duality: bounding and multipliers approach | [ch 5 of B1] |
| | Weak and strong duality theorems and complementary slackness theorem | [sc 6.1-6.3 of B3; ch 5 of B9] |
| | Dual Simplex. Economic interpretation | [p 208 of B1; ch 5 of B1] |
| 5 | apr23 | Duality by Lagrangian relaxation, Sensitivity Analysis | |
| | Duality by Lagrangian relaxation | [sc 2 of B4; sc 5.10] |
| | Sensitivity Analysis | [7.1 of B1; ch 10 B9 (BB)] |
| 6 | apr25 | Revised Simplex Method | Assignment 1 (FPMM) or Assignment 1 (PS) |
| | Farkas Lemma, Geometric interpretation | [sc 6.4 B3; A1] [ch 17 of B9 (BB)] |
| | Revised Simplex Method | [sc 4.1-4.3 B1; ch 7 B9 (BB)] [L5] |
| 7 | apr30 | Integer Programming - Modeling Examples | |
| | Modeling, Matchings, Packing, Covering, Assignments | [ch 1 of B2 (BB)] [ch 3 of B3] |
| 8 | may2 | Integer Programming - More on Modeling, Formulations, Relaxations | |
| | TSP, Facility location, Formulations, Relaxations, Primal and dual bounds, | [ch 2 of B2 (BB)] |
| | Properties of easy problems. | [sc 3.1 of B2 (BB)] |
| 9 | may7 | Well Solved Problems, Network Flows | |
| | Convex hull description, Total unimodular matrices, | [sc 3.2-3.5 of B2 (BB)] |
| | Network flows, Maximum flow, Min cost flow | [ch 7,7.1 of B4] |
| 10 | may14 | More on Network Flows | |
| | ILP in Excel | mincost.xlsx |
| | Network Flows algorithms and examples, Network Simplex | [sc 3.5 of B2] [ch 7 of B4] |
| | Valid inequalities | [sc 8.1 of B2] |
| 11 | may16 | Cutting Planes - Branch and Bound | |
| | Formulations, strength, inequalities. Chvatal Gomory cuts. | [sc 8.1-8.6 of B2 (BB)] |
| | Cutting plane algorithm. Gomory's fractional cutting plane algorithm, example. | [L8] |
| | Branch and Bound, example | [ch 7 of B2 (BB)] |
| 12 | may17 | More on Modelling and Preprocessing | [L9] [L10] [L11] |
| | SCIP output, | Assignment 2 |
| | More preprocessing, set covering preprocessing | |
| | Modelling tricks in IP, nonlinear programs, piecewise functions | [ch 9 of B5 (BB)] |
Exercises
| Sess. | Topic | Exercises |
|---|
| 1 | apr17 | Modelling in LP and the Simplex Method | Sheet 1 |
| 2 | apr19 | LP Software (note: in IMADA Terminal room!) | Sheet 2 |
| 3 | apr24 | Duality (note: in IMADA Terminal room!) | Sheet 3 |
| 4 | apr29 | Duality (note: in IMADA Terminal room!) | Sheet 4 |
| 5 | may1 | IP Modeling (in U140) | Sheet 5 |
| 6 | may8 | IP Modeling | Sheet 6 |
| 7 | may10 | Network flows | Sheet 7 |
| 8 | may15 | Network flows | Sheet 8 |
| 9 | may22 | Cutting Planes and Branch and Bound | Sheet 9 |
| jun11 | Rehearsal (at 9:00 in U154) | |
| jun13 | Question Time (at 9:00 in U26) | Sheet 10 |
Literature
Other Books
-
[B3] J. Matousek and B. Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007
-
[B4] J. Clausen and J. Larsen. Supplementary notes to networks and integer programming. Lecture Notes, DTU, 2009
-
[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.
-
[B7] Bernhard Korte and Jens Vygen. Combinatorial Optimization Theory and Algorithms Volume 21, 5th Edition, 2012
-
[B8] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications, Springer London, 2009 (Direct link to chp. 4, Flows in Networks.)
-
[B9] V. Chvatal. Linear Programming. W.H.Freeman, 1983
-
[B10] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and
A. Schrijver. Combinatorial optimization. Wiley-Interscience, 1998
[Among others, good for network simplex]
-
[B11] Robert Fourer, David M. Gay, and Brian W. Kernighan, AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Brooks
Cole, Publishing Company, 2003
-
[B12] Frederick S Hillier and Gerald J Lieberman, Introduction to Operations Research, 9th edition, 2010. ISBN: 0073376299
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
-
Obligatory project assignments. Internal examiner by
teacher. Pass/fail. The projects must be passed to attend the written
exam.
-
Written exam on June 18th, in U53 and U58, 4 hours from 9:00, 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 in to speed up deriving and writing
your solutions:
-
text editor in VERBATIM mode (EMACS + ORG mode)
-
AMPL
-
R, MATLAB, Maple, numpy.linalg (for matrix operations)
-
grapher in Mac to plot graphs
-
calculator for basic math operations
-
tikz for networks.]
-
Reexam: Oral exam, Danish 7 mark scale, external examiner.
Author: Marco Chiarandini
<marco@imada.sdu.dk>
Date: 2013-08-05 15:20:16 CEST
HTML generated by org-mode 6.33x in emacs 23
|