Date: Sunday September 4, 2016
Time: 9:00 – 17:00
Venue: World Forum, room: Africa
Email: rainer.koenig@uni-jena.de, Phone: +49 3641 532 1189
Mixed Integer Linear Programming (MILP) from Discrete Optimization can be applied to a vast number of problems and areas. In the meanwhile, the solvers for MILPs have progressed so considerably that Integer Programming is often superior to developing dedicated algorithms. MILP has many applications, most prominently in optimizing time tables and the traveling salesman problem. The beauty of this method is that it can employ a given list of rules or constraints limiting the search space on top of which the optimization is performed. In biochemistry, stoichiometric equations have been assembled for several thousand metabolites and reactions restricting the space of possible metabolic fluxes (at steady state) leading to Flux Balance Analysis as a MILP application1. We used MILP to optimize arrangements of cell-networks for identifying distinctively expressed pathways2 or to infer gene regulation3. Others used MILP to infer gene regulatory modules in cell-networks4 or regulatory pathways5. Within the tutorial, we will give an introduction into the principle idea of MILP, give some prominent problems to solve (such as knapsack, Sudoku) and will explain some of the above mentioned applications in bioinformatics. The participants will use their own laptops and an R-Studio and (academically free) solver (Gurobi) installation.
The course is addressed to bioinformaticians or biologists with a good working knowledge in basic calculus and linear algebra. The participants should bring their own laptops with a running R installation. We will install the free version of Gurobi during or just before the session, it is of course better, if the participants have Gurobi already installed before the session.
Morning session
9.00 Lecture (Oswald): Introduction to Mixed Integer Linear Programming (MILP)
1) Example: The oil refinement problem
2) What is a linear program?
3) Geometric view
3) Linear, Integer, and Mixed Integer Linear Programs
4) Relaxation
5) Solving MILP problems with the Gurobi software
10.15 Solving technical issues for the exercises (Oswald)
10:30 Coffee & tea
11.00 Tutorial part 1 (König, Oswald)
Participants use their own laptops and solve problems from exercise sheets, guided by the instructors, the participants may also follow the instructor’s examples on the screen
Exercises: A selection from the following problems: Oil refinement problem, Container ship problem, Burglar/Knapsack problem, Carpenter problem, Mobile provider problem, Sudoku
12:30 Lunch
13:30: Lecture (König): Applications in bioinformatics
1) Flux Balance Analysis: Putting up the problem, Flux Variability Analysis, Consistency Checking, the Model Building Algorithm (Jerby et al, 2010; Lewis et al, 2010; Orth et al, 2010)
2) Systematic pattern recognition in cellular networks (Piro et al, 2014; Schramm et al, 2010)
3) Identifying regulators of selected target genes by linear models (Schacht et al, 2014)
4) Constructing Support Vector Machines using MILP
14.15: Tutorial part 2 (König/Oswald)
Participants use their own laptops and solve problems from exercise sheets, guided by the instructors, the participants may also follow the instructor’s examples on the screen Exercise: Data analysis with MILP based Support Vector Machines using gene expression data from different studies and comparing and combining them, continuation of problems from the morning session.
15:00 Coffee & tea
15:30 Tutorial part 2 (König/Oswald) (continued)
17:00 End of tutorial