Diskrete Optimierung I / Discrete Optimization I

Braindump WS21/22 Dr. Andreas Bärmann

meta

English + German exam, explained everything twice

First written exam in history of the course, 15 minute oral exams before (according to MeinCampus)
Way easier than the exercises, doing the exercises + reading the entire script is highly(!) recommended
Lots of people had time trouble it seems. Might've also been due to the fact, that the branch and bound task was way more difficult/time-consuming than intended, but he said they'll adapt the grading accordingly to make it fair

No calculator allowed
1 sheet of DIN A4 paper (two pages, for some reason he didn't permit 2 sheets, 1 page each…)
ruler + pencil recommended

30 points in total, I think

content

1) Proof that P ⊆ {x ∈ K | x ≥ 0} is a „spitzes“ polyhedron (=has at least one corner)
4 points

2) Give the cone(E) representation (with E being finite) of rec(…) for P = {x ∈ R^5 | <a few polynomial inequalities>} and the intersection of P and {x ∈ R^5 | x_1 ≤ x_2}
6 points

3) Fourier-Motzkin, eliminate 3 Variables (4 inequalities) to check whether P is empty, values were chosen in a nice way if one chose a smart order of elimination
6 points

4) Branch-and-Bound graphically, insane amount of work, practice at home!
8 points

5) Show that P is full dimensional, show that <poly inequality> holds for P (trick, I think: recognize it's a cover inequality)
Show that <other poly inequality> induces a facet
6 points