Short Overview

The practical exercises for the lecture Optimization won't be programming exercises. Mostly you have to get familiar with an LP Solver, try to solve LPs and understand the results.

Assessment

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

There will be code reviews on each friday after the deadlines.

Exercise 1

You have to solve the exercises given in sheet 1 using MATLAB and glpk as a solver.

Send me your files via mail until Wednesday, 4. January 2017, 8:00 am.

Exercise 2: Flux Balance Analysis

Deadline: *Wednesday, 18. January 2017, 8:00 am.

Write a program that:

• reads in a metabolic network: A struct in a .mat file called "network" with:
  • S: the stoichiometric matrix
  • rev: the reversibility vector (rev(i) = 0: reaction i is not reversible, rev(i) = 1: reaction i is reversible)
  • rxns: names of the reactions
  • lb: lower bounds
  • ub: upper bounds
  • description: name of the network
• reads a second argument that is either BIOMASS or BLOCKED
• reads a third argument that is the output filename.
• depending on the given argument either:
  • computes flux distribution that maximizes the biomass production and fulfills the steady state assumption. The network will contain a reaction named "Biomass" whose rate has to be maximized.
  • determines for every reaction whether it is blocked or not.
• Output format:
  • in BIOMASS mode:
    • a cell (or a .txt file) with two columns where each row contains the reaction_id and the corresponding rate
    • the first row contains the Biomass reaction, the remaining reactions are ordered according to their index
  • in BLOCKED mode:
    • a vector which contains the names of the blocked reactions
    • they are ordered according to their index
• To download the zip file with the networks click here.

Exercise 3: n-Queens Problem

Deadline: 1.2.2017, 8:00 p.m.

Write a program that solves the n-Queens Problem:

Place as much queens as possible on a n x n chess board such that no two queens interfere. Thus:

• In each vertical line …
• In each horizontal line …
• In each diagonal line …

… is only one queen allowed.

Use MATLAB and glpk.

Write a function board = nQueens(n) that gives you a n x n matrix where the entries are 0 or 1. A 1 deontes that a queen was placed in the corresponding field.