Lectures and Colloquia during the semester





Konrad-Zuse-Zentrum für InformationstechnikBerlin
Takustraße 7, 14195 Berlin
Hörsaal (Raum 2005), Erdgeschoss


Lecture - 14.00 Uhr c.t.

Martin Grötschel - Konrad-Zuse-Zentrum Berlin

Semidefinite Relaxierungen in der kombinatorischen Optimierung

Abstract: Grosse Fallbeispiele schwieriger kombinatorischer Maximierungsprobleme kann man in der Regel nicht optimal lösen. Mit Primalheuristiken bestimmt man daher "gute" zulässige Lösungen und damit untere Schranken für den Wert einer Optimallösung. Zur Berechnung oberer Schranken lässt man einige Nebenbedingungen des Ausgangsproblems unberücksichtigt in der Hoffnung, dadurch ein praktisch einfacher zu lösendes Problem zu erhalten, dessen Optimalwert nicht allzuweit vom "wahren Optimum" abweicht. Auf diese Weise kann man problemspezifische Gütegarantien erzielen. Die Wahl einer geeigneten Relaxierung ist jedoch (immer noch) eine "Kunst".

Ein bewährter Ansatz ist die LP-Relaxierung (Weglassen der Ganzzahligkeitsbedingungen in einem gemischt-ganzzahligen Programm), die jedoch gelegentlich unerwartet schlechte Schranken liefert. Manchmal hilft dann die Methode der "semidefiniten Relaxierung", die in diesem Vortrag vorgestellt werden soll. Der "Trick" dieses Ansatzes besteht darin, das gegebene Problem so umzuformulieren, dass es als ein Optimierungsproblem erscheint, bei dem eine lineare Zielfunktion über der Menge der semidefiniten Matrizen zu optimieren ist, wobei u. U. weitere Nebenbedingungen erfüllt werden müssen.

In dieser Vorlesung wird u.a. auf semidefinite Relaxierungen des Stabile-Mengen-Problems und des Max-Cut-Problems eingegangen. Christoph Helmberg wird in der darauffolgenden Woche erläutern, wie man semidefinite Programme in der Praxis löst. In den begleitenden Kolloquiumsvorträgen von Arie Koster und Andreas Eisenblätter werden verschiedene Modellierungsmög/-lichkeiten für das Frequenzplanungsproblem erläutert und gezeigt, wie man dabei semidefinierte Optimierung einsetzen kann.


Colloquium - 16 Uhr s.t.

Arie Koster - Konrad-Zuse-Zentrum Berlin

Graph Coloring and Frequency Assignment

Abstract: Frequency Assignment Problems have been investigated by many researchers. Depending on the application and the goal of the researchers, a wide variety of models and solution techniques have been proposed. In this talk we give an overview of the main developments in recent years. We start our discussion with the basic properties of frequency assignment, and an overview of the areas of application. Next, the well known graph coloring problem is discussed, which can be viewed as a special case of frequency assignment. As early as the 1970s, the practical settings of frequency assignment problems inspired researchers to introduce several generalizations like T-coloring and list-coloring. In recent years, more and more application specific properties of frequency assignment have been incorporated in the mathematical models. Nowadays, the approaches can be classified by their objective. We distinguish Minimum Order Frequency Assignent, Minimum Span Frequency Assignment, Minimum Blocking Frequency Assignment, and Minimum Interference Frequency Assignment. The talk is concluded with an overview of the applied optimization techniques for each of these problem classes.


[top]