Hörsaal M/E28, Mathematikgebäude

Ein klassischer Ansatz zur Lösung nichtlinearer Optimierungsprobleme über binären Variablen ist die Linearisierung. Dazu werden zunächst neue Variablen eingeführt, die die nichtlinearen Terme modellieren; diese werden dann durch geeignete lineare Ungleichungen an die ursprünglichen Variablen gekoppelt. So entsteht ein lineares binäres Optimierungsproblem. Um dieses praktisch erfolgreich lösen zu können, etwa mit Schnittebenenverfahren, benötigt man eine gute Beschreibung des von allen zulässigen Lösungen aufgespannten Polytops. Da die Linearisierung aber üblicherweise für jede Variable einzeln geschieht, ist die entstehende Relaxierung meist schwach. Alternative Ansätze erreichen eine bessere Relaxierung, jedoch um den Preis einer stark vergrößerten Zahl von Variablen, was wiederum zu praktisch unlösbaren Problemen führt. Im Vortrag wird ein neuer Ansatz vorgestellt, der beiden Schwächen Rechnung trägt. Das allgemeine Problem wird durch Einführung weniger zusätzlicher Variablen auf ein quadratisches reduziert. Sofern das ursprüngliche Problem nur einfache (z.B. boolesche) Nebenbedingungen enthält, kann das resultierende quadratische Problem als unbeschränkt aufgefasst werden und ist somit zum Problem äquivalent, in einem Graphen einen maximalen Schnitt zu finden. Letzteres ist polyedrisch intensiv untersucht worden; alle Ergebnisse übertragen sich mithilfe der vorgestellten Reduktion automatisch auf das allgemeine Problem. Im Allgemeinen liefert die obige Reduktionsmethode allerdings ein beschränktes quadratisches Problem. Solche Probleme sind praktisch bereits sehr schwer zu lösen und wenig untersucht. Im zweiten Teil des Vortrags soll anhand eines Beispiels diskutiert werden, welche Effekte beim Übergang von einer linearen zu einer quadratischen Zielfunktion auftreten, und welche Lösungsansätze erfolgreich sein können. Zum Abschluss sollen außerdem einige Anwendungen der beschränkten quadratischen binären Optimierung vorgestellt werden, u.a. bei der Synthese digitaler Signale und bei der Steuerung von Motoren.

Vor dem Fachvortrag, welcher um 17.15 Uhr beginnt, findet noch ein Lehrvortrag von 16.30 - 17.00 Uhr mit dem Thema ``Eine kurze Einführung in die Nichtstandardanalysis`` statt.

PD Dr. Christoph Buchheim

Universität Köln