Goals: The students should get a deeper understanding of advanced mathematical notions and methods in discrete mathematics and optimization. They should be able to develop discrete mathematical models for problems in bioinformatics and systems biology, to apply suitable algorithms for their solution, and to analyse the results.
Contents: Linear programming, Simplex algorithm, duality, integer linear programming, branch and bound, cutting planes, branch and cut, constraint programming, local search and metaheuristics.
Times and Places (please see Calendar):
- The lecture will start on December 12, 2017 and end on February 15, 2018.
- The exercises will start on December 15, 2017 (Please note that the exercises are four hours)
Requirements for Aktive Teilnahme:
- to pass the exercises you need to pass the theoretical assignments, the programming assignments and the reviews
- if you successfully passed the exercises in a previous semester, i.e. all the requirements, you do not need to take the exercises again (although it is highly recommended)
- however partial results from previous semesters cannot be taken into account, e.g. if you only passed programming but not the review, you need to take programming again, as well.
Schedule:
Date | Lecture | Lecturer |
12.12.-21.12. | Linear Optimization | |
12.12.2017 | Lecture 1: Introduction to linear optimization | Bockmayr |
14.12.2017 | Lecture 2: Polyhedra and Simplex algorithm | Bockmayr |
15.12.2017 | Exercise (no assignments due) | Röhl |
19.12.2017 | Lecture 3: Simplex algorithm, application to metabolic networks | Bockmayr |
21.12.2017 | Lecture 4: Duality, complexity of LP | Bockmayr |
22.12.2017 | Exercise (theoretical assignment 1) | Röhl |
09.01.-25.01. | Integer Linear Optimization | |
09.01.2018 | Lecture 5: ILP - Introduction | Reinert |
11.01.2018 | Lecture 6: ILP - Modelling | Reinert |
12.01.2018 | Exercise (theor. assign. 2 + programming assign. 1) | Röhl |
16.01.2018 | Lecture 7: ILP - Branch-and-Cut I | Reinert |
18.01.2018 | Lecture 8: ILP - Branch-and-Cut II | Reinert |
19.01.2018 | Exercise (theoretical assignment 3) & Review 1 | Röhl |
23.01.2018 | Lecture 9: ILP - Lagrange I | Reinert |
25.01.2018 | Lecture 10: ILP: Lagrange II | Reinert |
26.01.2018 | Exercise (theor. assign. 4 + programming assign. 2) | Röhl |
30.01.-15.02. | Constraint Programming and Metaheuristics | |
30.01.2018 | Lecture 11: Constraint programming I | Bockmayr |
01.02.2018 | Lecture 12: Constraint programming II | Bockmayr |
02.02.2018 | Exercise (theoretical assignment 5) | Röhl |
06.02.2018 | Lecture 13: Constraint and integer programming | Bockmayr |
08.02.2018 | Lecture 14: Local search and metaheuristics I | Bockmayr |
09.02.2018 | Exercise (theor. assign. 6 + programming assign. 3) & Review 2 | Röhl |
13.02.2018 | Lecture 15: Local search and metaheuristics II | Bockmayr |
15.02.2018 | Rehearsal | |
22.02.2018 | Exam |
General notes regarding the exercises:
- to pass the course, you need to pass the exam in the end, and you need to pass the exercises (formal requirement "Aktive Teilnahme")
- to pass the exercises you need to pass the theoretical assignments, the programming assignments and the reviews
- both types of assignments will be available from the assignment field on the left
- if you successfully passed the exercises in a previous semester, i.e. all the requirements, you do not need to take the exercises again (although it is highly recommended)
- however, partial results from previous semesters cannot be taken into account, e.g. if you only passed programming but not the review, you need to take programming again, as well.
Theoretical assignments:
- there are six assignment sheets with 3-4 tasks each, every week one sheet is due
- you have to hand in 75% of all exercise problems. (An exercise problem counts, if it is clearly visible that a solution was attempted for some time. You do not have to have an exact solution.)
- you get to work on them in groups of two to three
- and the reviews will test the theory, as well, see below
Programming assignments:
- there are three programming assignments, one is due every two weeks
- you get to work on them in groups of two to three (same groups as for the theoretical assignments), please sign up to a group ASAP ("Section info" on the left)
- every two weeks each student have to explain the code
- failure to present a solution more than once means failing the exercises
- programming assignments are collected and graded
- programs need to build with MATLAB or octave using as solvers glpk, cplex or gurobi. R can be used as well, but here only glpk can be used as a solver.
- For each exercise you can score 3 Points:
3 Pts = program runs without errors
2 Pts = program contains small errors
1 Pts = program contains critical errors
0 Pts = no program submitted - You need to reach at least 75% of the combined points
Reviews:
- there are two reviews (smaller exams)
- they are graded and you need to reach at least 50% of the combined points to pass the exercises