Dirk Oliver Theis

VL Kombinatorische Optimierung WS 2011/12

In Komb-Opt, Teaching(DE) on October 12, 2011 at 13:01

Liebe Übungsteilnehmer,

Dieser Post ist der Vorlesung “Kombinatorische Optimierung” (WS 2011/12) gewidmet.

In den Responses (unten klicken) finden sich

  • die Übungsblätter
  • (hoffentlich) Ihre Fragen, Kommentare und Diskussionen zur VL und den Übungsblättern (gerne anonym)
  • Ankündigungen zur VL bzw zum Übungsbetrieb

Das jeweils neue Übungsblatt wird im Laufe des Donnerstags hochgeladen, und ein Link als Kommentar gepostet.

Übungen
Nur noch mal ganz kurz:

Donnerstag 9:15-10:45 G02 / 209
13:30-15:00 G14 / 125

Scheinkriterien

Für fortgeschrittene VLs wie der Kombinatorischen Optimierung gibt es keine Zettelkorrekturen mehr. Daher fällt das übliche Kriterium “50% der Übungszettelpunkte” für den Schein weg. Um Sie zu motivieren, trotzdem die Übungsaufgaben zu lösen (und damit Ihre Chancen zu verbessern, die Klausur zu bestehen), folgen wir seit einiger Zeit dem folgenden kleveren Ansatz (mit Varianten):

  1. Einziges Scheinkriterium ist Bestehen der Klausur mit mind. 50% der Punkte
  2. Jeder VL-Teilnehmer wird zur Klausur zugelassen
  3. In den Übungen werden die Übungsaufgaben zur Klausur von frewilligen Übungsteilnehmern vorgerechnet
  4. Für das Vorrechnen können Bonuspunkte zur Klausur gewonnen werden, und zwar 0%, 5% oder 10% pro Aufgabe, abhängig von der Qualität der dargestellten Lösung (10% gibt’s nur bei korrekter Lösung und perfekter Präsentation)
  5. Melden sich mehrere Freiwillige zum Vorrechnen der gleichen Aufgabe, so wird aus denjenigen mit geringster Punktzahl einer zufällig ausgewält
  6. Maximal 40% der Klausurpunkte können vor der Klausur erlangt werden

Außerdem soll es ein Programmierprojekt geben, mit dem Sie Klausurprozente schnorren können. Details dazu gibt es im Lauf der VL. Punkt (6) oben gilt inklusive der Projektpunkte.

Zum Schluss
den Hinweis auf meine Sprechzeiten und Kontaktdaten.

Viel Spaß bei der VL!

Advertisement

  1. Veröffentlichen Sie auch hier die Folien der VL?

    Reply
    farkas 12 October 2011 at 1pm

  2. Elektronische Ausgabe des Buches von Korte-Vygen

    Reply
    dirkolivertheis 12 October 2011 at 1pm

    • Lösung zur Aufgabe 3

      Bezeichne f(n) die Anzahl Pings für ein worst-case Beispiel von n-1 nicht frustrierten union-Operationen bei einer Grundmenge von n Elementen.

      Wir zeigen durch Induktion über die Anzahl der Union-Operationen, dass f(n) \le n\log n. (Wir machen nur den Induktionsschritt und sparen uns den Induktionsanfang.) Vor der letzten Union-Operation hatten wir zwei Mengen mit Kardinalitäten n_1 und n_2, wobei n_1 + n_2 = n. Wir nehmen an n_1 \le n/2 \le n_2 \le n, sonst vertausche die Indices. Es gilt

      f(n) \le n_1 + f(n_1) + f(n_2)
      \le n_1 + n_1 \log n_1 + n_2 \log n_2 \le n_1 + n_1 \log(n/2) + n_2 \log n
      = n_1 - n_1 \log 2 + (n_1 + n_2) \log n = n \log n

      Reply
      dirkolivertheis 20 October 2011 at 2pm

  4. Frage zur Aufgabe 2:
    Sind Graphen mit negativen Kreisen erlaubt und fängt der Algorithmus den Fall ab ob man einen Knoten mehrfach besucht?

    Reply
    Sebastian Schindler 14 October 2011 at 12pm

    • * Beliebige Kantengewichte, also alles ist erlaubt.

      * Der Algorithmus liefert einen kürzesten Weg. In einem Weg kommen per Definition keine Ecken mehrfach vor.

      Reply
      dirkolivertheis 14 October 2011 at 12pm

  5. Handout/Folien für das erste Kapitel:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/handout-k01.pdf

    Reply
    dirkolivertheis 14 October 2011 at 2pm

  6. Könnten Sie bitte das Skript möglichst frühzeitig online stellen, damit man in der Vorlesung damit arbeiten kann?
    Des weiteren suche ich noch nach dem 2. Übungszettel, um den bald bearbeiten zu können.

    Reply
    David 18 October 2011 at 10am

    • * Auf das Handout habe ich keinen Einfluss. Ich stelle die neuen Teile online, so bald ich sie bekomme. * Die Übungsblätter gibt’s immer Donnerstags, jede Woche eins. Blatt 2 gibt es also am kommenden Donnerstag.

      Reply
      dirkolivertheis 18 October 2011 at 11am

  7. Vielen Dank für die Information

    Reply
    David 18 October 2011 at 2pm

  8. Einige Skizzen von Themen möglicher Projekte für Bachelorarbeiten / Wissenschaftliche Projekte / Masterarbeiten finden sich hier:

    http://dl.dropbox.com/u/9875302/Teach/Projects/Nnrk/index.html

    In den nächsten Tagen werde ich noch mehr davon tippen!!

    Reply
    dirkolivertheis 20 October 2011 at 2pm

    • Es gibt ein neues Projekt, diesmal zum Programmieren.

      Reply
      dirkolivertheis 24 October 2011 at 12pm

    • Es gibt noch ein neues (Bachelor/Wiss/Master-fähiges) Programmierprojekt. Die beiden Projekte unterscheiden sich darin, dass es beim einen um Semidefinite Programme geht, beim anderen um Lineare Programme.

      Reply
      dirkolivertheis 26 October 2011 at 1pm

    • Mir ist irgendwie Aufgabe 1a nicht ganz klar… die Ausgabe einer falschen c-Distanz von s zu einem Knoten v setzt doch voraus, dass es mehrere Wege von s nach v gibt, sodass ich quasi einen Weg gewählt hab, der von einem anderen noch verbessert werden könnte… Von s aus zu den Knoten 2 und 4 gibt es doch aber nur jeweils einen gerichteten Weg. Wie soll der Algorithmus denn da falsche c-Distanzen ausgeben? Hab ich da nen Denkfehler, oder einfach nur die Aufgabe missverstanden.

      Reply
      Daniel 20 October 2011 at 3pm

  10. Hallo, eine Frage zu Aufgabe 2:
    Ist es noch erlaubt, wenn ich meinem kürzeste Wege Algorithmus zur Bestimmung des sichersten Weges, POSITIVE REELE Kantengewichte gebe?
    In der Vorlesung hatten wir ja immer bei den Alogrithmen die Gewichte aus Q+ vorausgesetzt.
    Und damit schließt sich auch eine weitere Frage an:
    Warum haben wir immer, die Gewichte aus Q+ voraussgesetzt und nicht aus R+.
    vielen Dank

    Reply
    farkas 22 October 2011 at 4pm

    • Guter Punkt!

      *Eigentlich* müssen Sie reelle Gewichte rational approximieren, aber den Effekt können Sie in dieser Aufgabe vernachlässigen.

      Reply
      dirkolivertheis 22 October 2011 at 7pm

  16. Programmierprojekt

    Implementieren Sie einen Max-Flow Algorithmus, und zwar entweder

    • * den Edmonds-Karp Algorithmus, oder
    • * den Preflow-Push Algorithmus.

    Bearbeiten Sie das Projekt in Gruppen aus ein bis drei Mitgliedern. In jedem Fall gelten folgende Regeln.

    • * Die Programmiersprache ist frei wählbar.
    • * Es dürfen kein Fremd-Code und keine Programmierbibliotheken verwendet werden, die Graphenalgorithmen enthalten. (Graphendatenstrukturen und Ein-Ausgaberoutinen sind erlaubt.)
    • * Für C++ und Java werden von uns Codefragmente zur Verfügung gestellt, die Graphendatenstrukturen und Ein-Ausgaberoutinen enthalten.
    • * Die Präsentation der Ergebnisse findet in der zweiten Vorlesungswochen nach Weihnachten statt (16.-20.1.2012).
    • * Die Präsentation besteht aus der Erläterung des Quellcodes, dem Compilieren (gegebenenfalls) und dem Laufen des Programs mit einigen von uns am Päsentationstermin gegebenen Flussnetzwerken (Datendateien).
    • * Aus jeder Gruppe wird unmittelbar vor der Präsentation von uns ein Teilnehmer ausgewählt, der die Präsentation komplett durchführt.
    • * Für die Präsentation gibt es zwischen 0 und 20 Prozent der Klausurpunkte.
    • * Alle bei der Präsentation anwesenden Gruppenmitglieder bekommen diese Punktzahl gutgeschrieben.
    • * Es gilt natürlich die 40-Prozent-Regel (”Nur höchstens 40% der Klausurpunkte können vor der Klausur erworben werden”).

    Die Struktur der Datendateien für die Flussnetzwerke werde ich später beschreiben.

    Reply
    dirkolivertheis 10 November 2011 at 2pm

  18. Die 13-15 Uhr Übung am Do, 17.11., muss leider Terminbedingt ausfallen. Sorry wegen der späten Benachrichtigung.

    Reply
    dirkolivertheis 16 November 2011 at 1pm

  22. …. und hier das 7. Blatt:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt07.pdf

    Echt schöne Aufgaben diesmal! :) :)

    Reply
    dirkolivertheis 24 November 2011 at 4pm

  23. Morgen,
    bei Aufgabe 2, darf das Problem nur auf ein perfektes Matching oder auch auf ein perfektes Matching mit minimalen Gewicht zurückgeführt werden?

    Reply
    farkas 27 November 2011 at 10am

  25. Das neue Blatt ist da (Blatt #8):

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt08.pdf

    Wer bei der 2. Aufgabe eine korrekte, vollständige Lösung vorrechnet (10%-Niveau nicht nötig), bekommt ein Mars/Schniggers/Twix (nach Wahl). :)

    Reply
    dirkolivertheis 1 December 2011 at 2pm

  27. Das 9. Blatt ist da:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt09.pdf

    Es gibt wieder einer Marsfrage: Wer bei der 2. Aufgabe eine korrekte und vollständige Lösung vorrechnet, gewinnt ein Mars/Sniggers/Twix.

    Der Marsgewinner der Aufgabe von Blatt 8 ist Daniel Laubrich. Der Preis wird ihm am kommenden Donnerstag bei einer feierlichen Marsverleihung übergeben werden.

    Reply
    dirkolivertheis 8 December 2011 at 2pm

  30. Die Folien für das 4. Kapitel sind hier:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/handout-k04.pdf

    Reply
    dirkolivertheis 15 December 2011 at 11am

    • Hmmm, die Folien zu Kapitel 4 sind doch irgendwie dünn. Hier noch einige der Sachen, die in der Vorlesung drankommen, aber nicht auf den Folien stehen.

      4.1: Greedy und Definition von Matroiden

       

      Satz. Es sei \mathcal I ein Unabhängigkeitssystem über E. Genau dann liefert der Greedy-Algorithmus für jedes c\colon E\to \mathbf Q_+ eine optimale Lösung, wenn folgendes gilt


      für jedes F \subset E gilt: jede inklusionsmaximale unabhängige Teilmenge von F ist auch kardinalitätsmaximal.

       

      Corollar. Genau dann ist M = (E,\mathcal I) ein Matroid, wenn eine, und damit jede, der folgenden Bedingungen gilt:

      1. Der Greedy-Algorithmus liefert für jedes c\colon E\to \mathbf Q_+ eine optimale Lösung
      2. Der Greedy-Algorithmus liefert für jedes c\colon E\to \mathbf Q eine optimale Basis
      3. für jedes F \subset E gilt: jede inklusionsmaximale unabhängige Teilmenge von F ist auch kardinalitätsmaximal
      4. für X,Y \in \mathcal I gilt: ist |Y| > |X| so existiert y\in Y\setminus X mit X\cup\{y\} \in\mathcal I

       

      4.2: Matroidpolytope und Polymatroide

       

      Lemma. Die Rangfunktion eines Matroids hat die folgenden Eigenschaften:

      • r(\emptyset) = 0
      • r ist isoton (monoton wachsend): X \subset Y \Rightarrow r(X) \le r(Y) für alle X,Y \subset E
      • r ist submodular: r(X\cup Y) + r(X\cap Y) \le r(X) + r(Y) für alle X,Y \subset E

      Zum Beweis der dritten Aussage, nehme eine maximale Unabhängige Teilmenge I von X\cap Y, und erweitere sie zu einer maximalen unabhängigen Teilmenge $I’$ von X\cup Y. Dann definiere I_X := I'\cap X und I_Y := I'\cap Y.

       

      In dem folgenden Satz beachte man, dass, im Fall eines Matroids, der Greedy-Alorithmus (f := r) genau die angegebene Lösung finden würde.

      Satz. Für jede Funktion f\colon 2^E \to \mathbf R mit den drei Eigenschaften des Lemmas gilt: Maximiert man w\colon E\to \mathbf R über das Polymatroid P(f), so kann man wie folgt eine Optimallösung konstruieren. Sortiere die Kanten absteigend: E = \{e_1,\dots,e_m\}. Sei h der größte Index, für den noch w(e_h) \ge 0 ist. Definiere F_k := \{e_1,\dots,e_k\}.

      x_k = \begin{cases}f(F_k) - f(F_{k-1}), & \mbox{falls } k \le h \\ 0, & \mbox{falls } k > h\end{cases}

      Ist f also ganzzahlig, so ist auch x ganzzahlig. Also hat man in dem Fall immer eine ganzzahlige Optimallösung — mit anderen Worten, das Polyeder ist ganzzahlig. Im Beweis des Satzes konstruiert man eine passende Lösung des dualen Linearen Programs. Hier gibt es eine Verbindung zu sogenannten TDI-Ungleichungssystemen, die in der Ganzzahligen Optimierung eine gewichtige Rolle spielen.

       

      Corollar. Sei M ein Matroid mit Rangfunktion r. Das Matroid-Polytop P_M ist gleich dem Polymatroidpolytop P(r).

      Zum Beweis benutzt man den Satz und argumentiert dann, dass alle ganzzahligen Lösungen des P(r)-definierenden Ungleichungssystems unabhängige Mengen von M sein müssen.

      Reply
      dirkolivertheis 22 December 2011 at 11am

  31. Hier ein paar neue Links:

    Musterlösung zu Blatt 9:
    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt09-solution.pdf

    Blatt 10:
    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt10.pdf

    Blatt 11:
    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt11.pdf
    Blatt 11 wird im Januar vorgerechnet. Ich stelle es jetzt schon online, weil es die Beispiele zu den beiden Vorlesungen in der nächsten Woche enthät.

    Reply
    dirkolivertheis 15 December 2011 at 4pm

  32. Gibt es diese Woche kein neues Übungsblatt? ;-(

    Reply
    Farkas 13 January 2012 at 10am

  33. Endlich, das 13. und letzte Blatt:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/blatt13.pdf

    Es gibt wieder eine Preisfrage. Die können Sie lösen, indem Sie Resultate aus verschiedenen Teilen der Vorlesung kombinieren.

    Reply
    dirkolivertheis 13 January 2012 at 6pm

    • Kleiner Tippfehler in Aufgabe 1: das “A” in der dritten Zeile sollte natürlich ein “U” sein.

      Und nur um noch mal klarzustellen: Wir interessieren uns für die Menge derjenigen Mengen U mit der folgenden Eigenschaft: es existiert eine Funktion f\colon U \to E mit …..

      Reply
      dirkolivertheis 17 January 2012 at 2pm

  34. Bitte tragen Sie sich für die Präsentation des Programmierprojektes ein:

    http://www.doodle.com/9gz92wryghn84bvg

    Reply
    dirkolivertheis 13 January 2012 at 6pm

  35. Modulprüfungen

    Wenn Sie in den Semesterferien die Modulprüfung für die VL ablegen wollen, tragen Sie sich bitte hier für einen Termin ein:

    https://terminplaner.dfn.de/foodle.php?id=7gzb6qrv65eb2ys8

    Reply
    dirkolivertheis 18 January 2012 at 3pm

  36. Hinweis zur Klausur

    Es sind alle Hilfsmittel erlaubt, es sei denn, sie könnten Kommunikation ermöglichen. Insbesondere dürfen Handys nicht als Taschenrechner verwendet werden.

    Reply
    dirkolivertheis 19 January 2012 at 10am

  37. Wettbewerb

    Gerade ist ein Wettbewerb für Studenten im Bereich Modellierung/Optimierung ausgeschrieben. Dreiergruppen von Studenten werden mit Modellierungsproblemen konfrontiert, die sie natürlich lösen sollen. Dabei werden sie von einem Mentor betreut (das wäre ich). Das Finale wird in den USA stattfinden.

    Wer Interesse hat, daran teilzunehmen, möge sich bitte melden!!!!

    Reply
    dirkolivertheis 26 January 2012 at 3pm

  38. Hier endlich die Handouts der letzten beiden Kapitel:

    http://dl.dropbox.com/u/9875302/Teach/Kombopt/handout-k05.pdf
    http://dl.dropbox.com/u/9875302/Teach/Kombopt/handout-k06.pdf

    Bei der Gelegenheit möchte ich Sie auf meine Vorlesung im Sommersemester hinweisen: http://dirkolivertheis.wordpress.com/2012/01/27/algrndstruct/

    Reply
    dirkolivertheis 27 January 2012 at 1pm

  39. Thema Klausur: Jeder Klausurteilnehmer sollte inzwischen eine Email mit seinem Ergebnis erhalten haben.

    Wenn Sie Fragen haben oder Ihre Klausur einsehen wollen, kommen Sie bitte in meine Sprechstunde: http://dirkolivertheis.wordpress.com/office-hours/

    Reply
    dirkolivertheis 27 January 2012 at 1pm

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Follow

Get every new post delivered to your Inbox.