======  Numerical Aspects of Linear Integer Programming (NALIP) ======

**Prüfer:** Florian Rösel (Beisitzerin Martina Kuchlbauer)
**Datum:** 24.07.2023
**Prüfungsdauer:** 15 min
**Note: 1.0**

Relativ einfache Prüfung, die auch allein mit dem Skript (ohne Übungen) machbar ist. Im Nachhinein hätte ich weniger in die Tiefe gelernt (evtl. z.B. weggelassen, wie man für Phase I im bounded Simplex mit unzulässigen Slack variablen den Algorithmus optimieren kann (im Skript Kapitel 3.2.3)) und mehr in die Breite.

**Fragen:**
  - F: Hast du die Übungen gemacht? Dann könntest du jetzt darüber ein wenig reden.
    * A: Eher weniger.
  - F: Okay, wir haben zwei Formen von LPs kennengelernt, schreib die mal hin.
    * A: [In natürlicher Form + Standardform aufgestellt]
  - F: Beschreibe mal den Simplex für LPs in Standardform beschreiben 
    * A: INPUT: Basis B mit zulässigem x_B; BTRAN:... 
  - F: Bei w <= 0 ist das Problem unbounded, warum?
    * A: Er wollte den algebraischen Beweis dafür, ich habe es graphisch begründet, was wohl auch okay war: w ist der Richtungsvektor der Kante, entlang der man sich bewegt, wenn man j in die Basis aufnimmt. Wenn w_i jetzt negativ ist, heißt das, dass man sich von dem constraint wegbewegen muss, um seine Zielfunktion zu verbessern (anstatt darauf zu), ohne je irgendwo anzustoßen. -> Unbounded.
  - F: Laufzeiten der einzelnen Schritte:
    * A: BTRAN O(m^3), Pricing O(m^2) (glaube O(n*m) wäre genauer gewesen), FTRAN O(m^3), Ratio-Test O(m), Update O(m)
  - F: Wenn man jetzt ein Problem mit riesigem n hat (z.b. m=1000, n=10 Mio.). Wie kann man dann beim Pricing die Laufzeit verbessern?
    * A: Habe erst angefangen mit sparse Matrizen angefangen, falls in dem Problem viele 0er sind. Bin dann später auf die modernen Pricing-Methoden gekommen.
  - F: Was für Arten haben wir denn kennen gelernt?
    * A: Bland, lexicographic Rule, Dantzig, Partial Pricing, Multiple Partial Pricing, Devex,
  - F: Wie funktioniert Dantzig denn?
    * A: ...
  - F: Wie schlägt sich denn Dantzig am Anfang?
    * A: Am Anfang gut, weil man schnell negative z findet, und nicht lange suchen muss. Viele normale Nachteile gelten aber trotzdem noch: konvergiert langsam, numerisch instabil.
  - F: Wir haben jetzt noch bisschen Zeit, was möchtest du so sonst noch machen? Phase I? Bounded LP? Sensitivitätsanalyse? 
    * A: Keine Ahnung... Sensitivitätsanalyse.
  - F: Was passiert denn wenn man ein bereits gelöstes LP hat, und sich nun das B geringfügig verändert? Wenn jetzt z.B. eine höhere Genauigkeit gewünscht ist?
    * A: (Es gab erst etwas hin und her, weil ich die Frage falsch verstanden habe). Bei einem Problem in Standardform ohne Slackvariablen? Dann ist das constraint verletzt => B nicht mehr primal zulässig => man braucht eine neue optimale Lösung. Aber da das z_N davon nicht beeinflusst wird, und für die optimale Lösung. z_N >= 0 gilt, ist die Basis immer noch dual zulässig => Man kann den dualen Simplex nehmen um die neue optimale Lösung. zu berechnen.
  - F: Tatsächlich ist es bei geringfügigen Änderungen von b so, dass das constraint nicht verletzt ist und damit die berechnete Lösung. optimal bleibt.
    * A: Achso, bei sooo geringfügigen Änderungen. Wenn Änderungen. innerhalb des Toleranzbereichs bleiben, im Skript lag der bei < 10^(-6), bleibt das LP natürlich zulässig.