Liebe AGTler,
das 9. Übungsblatt ist ab heute online. In Aufgabe 2 gibt es dieses Mal einen größeren Teil zum Linearen Programmieren mit OPL CPLEX.
Für alle, die noch Übungspunkte brauchen, ist das eine gute Möglichkeit Zusatzpunkte zu sammeln und für alle anderen ist es sicher interessant auch ein bisschen praktische Erfahrung mit Linearer Programmierung und LP-Solvern zu bekommen.
Viel Spaß und Erfolg beim Bearbeiten!
Johannes
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