Liebe Übungsbearbeiter und -bearbeiterinnen,
auf dem 9. Übungsblatt letzte Woche ging es in Aufgabe 2 u. a. darum, ILPs zum Knotenfärben zu erstellen. Im ersten ILP durfte jede Variable einen beliebigen ganzzahligen Wert annehmen, während im zweiten ILP nur eine Variable ganzzahlig sein durfte und alle anderen Variablen binär sein mussten, also nur den Wert 0 oder 1 annehmen durften.
In (Zusatz)aufgabe 2 g) sollten diese ILPs anhand einer größeren Anzahl von zufällig generierten Graphen verglichen werden. Ein paar einzelne Übungsgruppen haben diese Aufgabe bearbeitet, was sehr lobenswert ist. Eine Gruppe hat hier sehr schöne Plots erstellt, die für verschiedene Graphenklassen die Laufzeit der zwei ILPs anhand der Knotenzahlen anzeigen. Dort sieht man auf einer logarithmischen Skala sehr schön, dass bei größer werdenden Knotenzahlen n die Laufzeit für das erste ILP mit den Ganzzahlen sehr viel stärker steigt als für das zweite ILP mit (fast) nur binären Variablen, obwohl letzteres deutlich mehr Constraints besitzt. Binäre Variablen scheinen also der deutlich bessere Ansatz zu sein. Schauen Sie sich die Plots gerne einmal an, sie sind jetzt auf WueCampus verfügbar.
Viele Grüße,
Johannes Zink
auf dem 9. Übungsblatt letzte Woche ging es in Aufgabe 2 u. a. darum, ILPs zum Knotenfärben zu erstellen. Im ersten ILP durfte jede Variable einen beliebigen ganzzahligen Wert annehmen, während im zweiten ILP nur eine Variable ganzzahlig sein durfte und alle anderen Variablen binär sein mussten, also nur den Wert 0 oder 1 annehmen durften.
In (Zusatz)aufgabe 2 g) sollten diese ILPs anhand einer größeren Anzahl von zufällig generierten Graphen verglichen werden. Ein paar einzelne Übungsgruppen haben diese Aufgabe bearbeitet, was sehr lobenswert ist. Eine Gruppe hat hier sehr schöne Plots erstellt, die für verschiedene Graphenklassen die Laufzeit der zwei ILPs anhand der Knotenzahlen anzeigen. Dort sieht man auf einer logarithmischen Skala sehr schön, dass bei größer werdenden Knotenzahlen n die Laufzeit für das erste ILP mit den Ganzzahlen sehr viel stärker steigt als für das zweite ILP mit (fast) nur binären Variablen, obwohl letzteres deutlich mehr Constraints besitzt. Binäre Variablen scheinen also der deutlich bessere Ansatz zu sein. Schauen Sie sich die Plots gerne einmal an, sie sind jetzt auf WueCampus verfügbar.
Viele Grüße,
Johannes Zink