Lineare Programmierung / Ganzzahlige Lineare Programmierung / Semidefinite Programme

Lineare Programmierung und Ganzzahlige Lineare Programmierung

Obwohl Lineare Programmierung und Ganzzahlige Lineare Programmierung zum üblichen Methodenrepertoire der kombinatorischen Optimierung gehören, konnten sie sich erst in den letzten Jahren im Timetabling-Bereich etablieren [Bau97]. Die Größe der Problemstellung machte ein Herangehen mit Branch & Bound-Verfahren unmöglich und ist auf in Schulen verfügbarer Hardware auch heute noch nicht praktikabel. Positive Ergebnisse bezüglich der Gutartigkeit der jeweiligen Polytope, wie sie z.B. beim Vehicle Routing [RF88] gegeben sind, liegen noch nicht vor.
Dafür kann man - entsprechende Flexibilität bei der jeweiligen Institution voraussetzend - nichtganzzahlige Lösungen dennoch anwenden, indem man entsprechend dem kleinsten gemeinsamen Vielfachen der Nenner der Ergebnisse viele Wochen wählt und dann ganze Stunden entsprechend den jeweiligen Bruchteilen verteilt. Dieses Verfahren wird aber in der Regel nur bis zu einer Größe des Hauptnenners von 2 eingesetzt.

Lineare Programme dienen daher primär als Lieferant unterer Schranken für Branch & Bound Verfahren. Zudem sind lineare Zielfunktionen für das Timetablingzumeist nicht ausreichend. So ist es z.B. unbefriedigend, wenn 10 Lehrer keine ungünstigen Stunden haben, einer aber deren 10. Diesem kann abgeholfen werden, indem man annimmt, daß es für jedes (lineare) Kriterium eine von einem Parameter abhängige Funktion gibt, so daß für alle u (z.B. ) gilt, daß jede Lösung mit befriedigender ist, als jede, bei der eine der Ungleichungen gebrochen wird. Das kleinste u, das noch eine solche Lösung zuläßt, könnte mit binärer Suche dann relativ schnell gefunden werden. Im Timetablingließe sich eine solche Funktion zumeist sehr leicht angeben, da z.B. eine gleiche Nachmittagsbelastung der Klassen o.ä. zu den normalen Anforderungen zählt.
Wollte man aber versuchen, diese Methode zur weiteren Optimierung einzusetzen, so stünde man vor dem Problem, eine Teilmenge der auswählen zu müssen, für die der Wert von ab sofort anders gewählt werden soll. Diese Wahl dürfte aber wieder einen exponentiellen Suchaufwand verlangen. Schränkt man die Suche auf ganzzahlige Probleme ein, so müßte dann allerdings der entsprechende ILP-Algorithmus für jeden Wert von u erneut gestartet werden.

Eine Darstellung der Probleme als ILPs wurde bei ihrer Einführung bereits gegeben. Lineare Programme mit mehreren zehntausend Variablen - bei einer mittleren Schule ca. 30000 - können beim heutigen Stand der Technik selbst auf Microcomputern schnell gelöst werden. Relative gewichtete Nebenbedingungen können allerdings nicht modelliert werden. Bei ILPs liegt die Grenze im allgemeinen noch etwas niedriger [MK98], d.h. im Bereich einiger tausend Variablen und es gibt bereits Untersuchungen zu Problemen geringer Größe, bei denen sich ILP z.B. Simulated Annealing überlegen zeigte [BGH97].

Offenbar bilden Pläne, in denen der Lehrer jeweils nur eine Stunde hat, eine Basis des , über dem diese Funktion modelliert werden müßte. Bei je einer Stunde liegt aber keine Springstunde vor. Des weiteren liegt keine Springstunde vor, wenn der Lehrer gar keinen Unterricht hat. Somit wäre eine entsprechende affin-lineare Funktion auf den Vektoren einer Basis und auf dem Nullpunkt Null und somit identisch gleich Null.
Dennoch könnte man die Springstundenminimerung in der Form hinzufügen, wobei die entsprechenden Stunden in der Reihenfolge rml im Plan auftreten. a kann somit nur dann Null sein, wenn m keine Springstunde ist.

Semidefinite Programme

Einfache quadratische konvexe Probleme lassen sich mit Hilfe semidefiniter Programmierung darstellen. Diese wiederum kann durch pfadverfolgende Methoden [VB96] oder der Karmakar-Methode für lineare Programme ähnelnde Verfahren [Ali95] in polynomieller Zeit ausgewertet werden. Sie wird insbesondere in Approximationsalgorithmen für Graphenfärbungsprobleme [Hoc97] und der Relaxierung von ILP-Problemen eingesetzt.
Ein semidefinites Programm ist gegeben durch eine Menge von Variablen , eine lineare Zielfunktion und durch eine Menge symmetrischer Matrizen . Das Optimierungsproblem hat die Form

Dies kann z.B. dazu verwendet werden, eine gleichmäßige Belastung der Lehrer zu gewährleisten: Wäre z.B. durch ein Maß für die Belastung eines Lehrers gegeben, so könnte der Ausdruck

minimiert werden. Hierzu muß zunächst das LP, das die gültige Menge beschreibt, in ein Teil des SDP überführt werden. Jedes LP aus Kapitel 2 kann hier eingesetzt werden: Formt man zunächst die Nebenbedingungen zu für alle i um und hat A k Zeilen, so kann man durch Wahl der oberen Einträge als

und

wählen, was die entsprechenden Bedingungen garantiert.
Um die obige Optimierungsaufgabe einzubinden, seien zunächst die Hilfsvariablen und t hinzugefügt. Diese Eigenschaft der ist linear und kann daher analog zum obigen Vorgehen sichergestellt werden. Nun fügt man weitere Matrizen und zu der Menge hinzu, so daß sich als deren Summe eine auf der Diagonalen liegende Teilmatrix der Form

ergibt. Wie man [VB96] entnehmen kann, sorgt dies dafür, daß gilt. Strebt man nun die Minimierung von t an, so wird offensichtlich auch 4.1 minimiert.

Da die Ränder der Lösungsmenge nicht mehr von konvexen (|I|-1)-dimensionalen Polyedern gebildet werden, wie dies bei den LPs zumeist der Fall ist, muß die Lösung nicht mehr zwangsläufig in einer Ecke liegen, und somit können hier selbst bei ganzzahligen Ecken nichtganzzahlige Lösungen auftreten.