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:

1. F: Hast du die Übungen gemacht? Dann könntest du jetzt darüber ein wenig reden.
   • A: Eher weniger.
2. F: Okay, wir haben zwei Formen von LPs kennengelernt, schreib die mal hin.
   • A: [In natürlicher Form + Standardform aufgestellt]
3. F: Beschreibe mal den Simplex für LPs in Standardform beschreiben
   • A: INPUT: Basis B mit zulässigem x_B; BTRAN:…
4. 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.
5. 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)
6. 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.
7. F: Was für Arten haben wir denn kennen gelernt?
   • A: Bland, lexicographic Rule, Dantzig, Partial Pricing, Multiple Partial Pricing, Devex,
8. F: Wie funktioniert Dantzig denn?
   • A: …
9. 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.
10. 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.
11. 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.
12. 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.