======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 Talked about each of the tasks in the beginning 30 points in total, I think Not sure about the order ==== 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 | } 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 holds for P (trick, I think: recognize it's a cover inequality)\\ Show that induces a facet\\ 6 points