Prüfung: Numerical Aspects of Linear Integer Programming
Prüfer: Dr. Andreas Bärmann
Datum: 26.08.2021
Dauer der Prüfung: ca. 15 min
Note: 1×1.3 (→ 1.0 mit Notenbonus von 0.3, den man durch Übungen erwerben kann) und 1×1.0

Prüfung wurde zweimal fast genauso gehalten. An der Tafel waren ein paar Formeln aus der Vorlesung als Formelsammlung hingezeichnet, die man zum Erklären als auch als kleine Erinnerung verwenden konnte.

Fragen:

Phase 1 des Simplex-Algorithmus

• F: Problem in Standardform aufstellen
  A: min c^Tx, s.t. Ax = b, x >= 0
• F: Das = in Ax = b wird durch ein ≤ ersetzt. Zudem sei b >= 0. Wie findet man eine gültige Basis?
  A: Für Simplex muss man sowieso Schlupfvariablen einführen, diese kann man dann direkt als Basis verwenden.
• F: Was passiert nun, wenn man die Bedingung b >= 0 streicht? Wie löst man das Problem?
  A: Die Schlupfvariablen bilden nicht mehr unbedingt eine Basis, da die Bedingung x >= 0 eventuell verletzt ist. Einführen von künstlichen Variablen mit negativen Koeffizienten und Starten der Phase 1.
• F: Wie ist die Zielfunktion für das Phase 1-Problem zu wählen?
  A: Für künstliche Variablen y entsprechend 1^Ty. Wenn die Optimallösung des Problems 0 ist, dann existiert eine Basis für das ursprüngliche Problem.
• F: Welches Problem kann auftreten, wenn der Simplex mit dem Phase-1-Problem mit optimalen Ergebnis terminiert?
  A: Im Falle einer degenerierten Basis können die künstlichen Variablen trotzdem in der Basis vorkommen. Ausführen weiterer Simplex-Schritte, um schrittweise künstliche Variablen aus Basis zu entfernen.
• F: Ist das immer möglich?
  A: Nein, aber wir fordern an unsere Probleme, dass diesen vollen Zeilenrang haben. Andernfalls können wir einfach Zeilen aus dem Problem streichen, um vollen Zeilenrang zu erhalten.

Pricing-Verfahren

• F: Erläutere kurz das partielle Pricing. Warum ist das besser als Dantzig und weshalb eignet sich das vor allem am Beginn des Simplex?
  A: Aufteilen der Menge der Nichtbasisvariablen in Abschnitte. Betrachten der Abschnitte separat und Minimumsbildung pro Abschnitt. Man muss dabei im Regelfall nicht alle Nichtbasisvariablen betrachten (im Gegensatz zu Dantzig); vor allem zu Beginn des Simplex gibt es viele Nichtbasisvariablen, die potenziell die Zielfunktion verbessern.
• F: Was ist die Grundidee hinter dem Verfahren des steilsten Abstiegs?
  A: Ausführliche Erklärung, was der Vektor der reduzierenden Kosten bedeutet, warum der misleading sein kann (→ Auswirkung auf andere Basisvariablen nicht berücksichtigt), wie man den Richtungsvektor u berechnet, und ein paar Rückschlüsse auf die Länge des Vektors u.
  → Man wählt diejenige Variable mit negativen reduzierenden Kosten, welche in der Zielfunktion den steilsten Ansteig in Bezug auf das entsprechende u verursacht.
• F: Warum ist das ineffizient? Wie kann man das besser machen?
  A: Man muss für jede mögliche eintretende Variable k ein FTRAN durchführen (d. h. ein ganzes Gleichungssystem lösen). Stattdessen Update-Regeln von Goldfarb verwenden.
• F: Auf der Tafel stehen ein paar Gleichungen aus der Vorlesung zum Goldfarb. Erläutere diese mal und erkläre, was wie aufwendig zu berechnen ist.
  A: Im Wesentlichen wurden hier die Update-Regeln aus der Vorlesung zitiert. Man durfte jeweils den Berechnungsaufwand der drei Summanden in der Formel beschreiben.
• F: Wir haben noch das Devex-Pricing kennengelernt. Wie unterscheidet sich das vom Goldfarb?
  A: Optimierung des Goldfarb mittels des Referenzsystems und Maximumsbildung beim Update anstatt Summenformel (wodurch auch die Formel deutlich einfacher zu berechnen ist).
• F: Durch die Maximumsbildung werden die Pricing-Werte für eine Variable k ja immer größer. Wie man dem entgegensteuern?
  A: Reinitialisierung des Referenzsystems auf die Nichtbasisvariablen bei zu großer Abweichung. Die Approximationswerte T_k werden in diesem Fall auf 1 für alle Nichtbasisvariablen gesetzt (hier kleiner Verweis auf den Ausdruck u_k = e_k - (Y_k)^R).

Dünnbesetzte Matrizen

• F: Man kann ja für eine Matrix A eine LU-Zerlegung bestimmen, d. h. A=LU schreiben. Diese verwendet man, wenn man für viele verschiedene rechte Seiten b das Gleichungssystem Ax=b lösen möchte.
  Wie kann man hier die Rückwärts-/ und Vorwärtssubstitution bei dünnbesetzten Matrizen beschleunigen?
  A: Graph-Konstruktion aus dem Skript: Damit lässt sich herausfinden, an welchen Stellen im Vektor x überhaupt Nicht-Null-Einträge vorkommen können. (Weitere Details siehe Skript)

Allgemein entspannte Atmosphäre und faire Fragen. Der Stoff ist vollständig im Skript abgedeckt. Man sollte sich aber gut mit dem Stoff auskennen und vor allem verstehen, warum man bestimmte Dinge tut. Beweise sind keine gefragt, viel mehr sind die Grundideen und die Auswirkungen auf die Laufzeit etc. wichtig.