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