Verleihung des Dissertationspreises 1998

von JOSEF STOER, WÜRZBURG

Anläßlich der Eröffnungsveranstaltung der OR 98 in Zürich verlieh die GOR drei jeweils mit DM 2500,- dotierte Preise für hervorragende Dissertationen. Die Preisträger waren Dr. Thomas Christof (Universität Heidelberg), Dr. Frank Dellmann (Universität Essen) und Dr. Kathrin Fischer (Universität Hamburg).

Herr Dr. Thomas Christof promovierte an der Universität Heidelberg mit der Dissertation
»Low-dimensional 0/1 polytopes and branch-and-cut in combinatorial optimization« Sein Doktorvater ist Prof. Reinelt.

Seit ihrer Entwicklung in den achtziger Jahren gehören branch-and-cut-Verfahren zu den leistungsfähigsten Ansätzen zur exakten Lösung schwieriger kombinatorischer Optimierungsprobleme. Sie basieren auf (partiellen) linearen Beschreibungen von den jeweiligen Problemen zugehörigen 0/1-Polytopen, die als konvexe Hülle der charakteristischen Vektoren der zulässigen Lösungen definiert sind. Der Erfolg eines branch-and-cut-Algorithmus hängt wesentlich davon ab, wie genau man diese Polytope beschreiben kann und für welche Ungleichungen der linearen Beschreibung man auch Separationsverfahren entwickeln und einsetzen kann.

Dazu sind einmal für ein Optimierungsproblem Klassen von Facetten-definierenden Ungleichungen für die entsprechenden 0/1-Polytope zu finden, und man hat bei der Lösung eines konkreten Einzelproblems ein Separierungsproblem zu lösen, nämlich für einen gegebenen Vektor entweder festzustellen, daß er alle Ungleichungen der Klasse erfüllt, oder eine verletzte Ungleichung anzugeben.

Hier setzt die Dissertation von Herrn Christof an: Sie besteht aus zwei Komponenten. Zum einen entwickelt Herr Christof neue Verfahren zu einer vollständigen linearen Beschreibung der Polytope, die zu kombinatorischen Optimierungsproblemen kleinerer Größenordnungen gehören. Er zeigt, wie sich für bestimmte Klassen von 0/1-Polytopen die Ergebnisse für charakteristische Polytope niederer Dimension auf Beispiele von Problemen beliebiger Größe übertragen lassen. Er bestimmte auf diese Weise bislang unbekannte lineare Beschreibungen mehrerer kombinatorischer Polytope. Zum anderen untersucht er, wie die von ihm hier gewonnenen Informationen zu völlig neuartigen und äußerst effektiven Separierungsmethoden in branch-and-cut-Algorithmen ausgenutzt werden können.

Herr Christof zeigt die Leistungsfähigkeit seiner Methoden an einem wichtigen Problem aus der Molekularbiologie, dem Kartierungsproblem für Chromosomen, das sich als ein kombinatorisches Optimierungsproblem formulieren läßt. Seine neuen Modelle und Lösungstechniken sind früheren Ansätzen weit überlegen.

Die Dissertation von Herrn Dr. Frank Dellmann trägt den Titel »Verarbeitung von partiellen Wahrscheinlichkeitsinformationen in entscheidungsunterstützenden Systemen« und ist 1996 unter der Leitung seines Doktorvaters Prof. Hansohm an der Universität Essen entstanden.

Entscheidungsunterstützende Systeme (decision support systems) sollen bei der Behandlung von Problemen helfen, bei deren Lösung zwar die Anwendung von Methoden aus dem Operations Research und der Statistik wichtig ist, aber bei denen die Lösung des Problems nicht so weit automatisiert werden kann, daß die Entscheidung ohne die Erfahrung und Intuition des Entscheidungsträgers gefällt werden kann.

Z.B. müssen in der ökonomischen Praxis Entscheidungen unter Unsicherheit getroffen werden. Dabei läßt sich Unsicherheit in vielen Fällen nicht in Form von Punktwahrscheinlichkeiten ausdrücken, sondern durch partielle Wahrscheinlichkeitsinformationen, z.B. in Form von oberen und unteren Schranken für unbekannte Wahrscheinlichkeiten, die vom Entscheidungsträger auf der Grundlage von persönlichen Erfahrungen, Meinungen oder Gefühlen formuliert werden.

Die Arbeit von Herrn Dellmann liefert einen theoretischen Ansatz zur Verarbeitung partieller Wahrscheinlichkeitsinformationen in EUS durch eine Integration von probabilistischer Logik, Wahrscheinlichkeitstheorie und Entscheidungstheorie bei partiellen Informationen (PI). Dabei wird das Ziel verfolgt, die verfügbaren Wahrscheinlichkeitsinformationen möglichst vollständig zu berücksichtigen. Um sein Konzept zum Erfolg zu führen, mußte Herr Dellmann eine Reihe von wissenschaftlicher Detailarbeit leisten (Konsistenzprüfung der partiellen Wahrscheinlichkeitsinformationen, Berücksichtigung strikter Ungleichungen bei linearen partiellen Informationen, Modifikation und Erweiterung der linearen Modelle auf nichtlineare Informationsmodelle) und verschiedene, meist getrennt betrachtete Wissensgebiete nutzen (nichtlineare, nichtkonvexe Optimierung, betriebswirtschaftliche Entscheidungsprozesse, objektorientierte Paradigmen beim Systementwurf).

Diese theoretischen Ansätze werden in der Arbeit für den Anwendungsbereich der Realinvestitionsentscheidungen in einem entscheidungsunterstützendem System prototypisch umgesetzt und so die Praktikabilität des Konzepts nachgewiesen.

Frau Dr. Kathrin Fischer hat ihre Promotion 1996 an der Universität Hamburg abgeschlossen, ihr Doktorvater ist Prof. Seelbach am Institut für Logistik und Transport. Ihre Dissertation trägt den Titel »Standortplanung unter Berücksichtigung verschiedener Marktbedingungen«

Sie kombiniert in ihrer Arbeit unter einer einheitlichen spieltheoretischen Sichtweise drei große Gebiete, die klassische OR-Standortplanung, die Gleichgewichtstheorie und die Theorie ökonomischer Konkurrenzsituationen, um bei der Standortplanung Marktbedingungen zu berücksichtigen.

Ziel der Arbeit von Frau Fischer ist es zunächst, die unterschiedlichen Ansätze zur Planung von Standorten unter einem einheitlichen Blickwinkel zu betrachten. Insbesondere berücksichtigt sie den Einfluß des Absatzbereichs unter verschiedenen Marktbedingungen, die bisher bei der klassischen Standortplanung weitgehend vernachlässigt wurden. So werden alle Konzepte in ein Schema eingeordnet, in dem nicht nur die Anbieterzahl und ihre räumliche Verteilung, sondern auch nachfrageorientierte, kosten- und versorgungsorientierte Kriterien und die dem planenden Unternehmen zur Verfügung stehenden wirtschaftlichen Strategien eine wichtige Rolle spielen.

Auf diese Weise lassen sich Entscheidungen über die Produktionsverhältnisse und damit die Beschaffung von Produktionsfaktoren unter bestimmten Voraussetzungen in die klassische Standortplanung integrieren. Als einheitliche Lösungsansätze für Standortprobleme werden Gleichgewichtskonzepte aus Spieltheorie, Nash-Gleichgewichte bzw. für dynamische Spiele teilspielperfekte Gleichgewichte angewendet. So erfolgt die Abbildung vollständiger Konkurrenz auf räumlich unterschiedlichen Märkten durch Gleichgewichtsmodelle, die z.B. als Komplementaritätsprobleme formuliert werden können.

Ebenso lassen sich allgemeine räumliche Oligopole unter Mengenkonkurrenz als Komplementaritätsprobleme beschreiben und räumliche Gleichgewichte und Monopole als Grenzfälle räumlicher Oligopole ableiten. Die Probleme, die Frau Fischer so erhält, haben eine spezielle verschränkte Struktur. Sie führen zwar wieder auf Optimierungsprobleme in Netzwerken, aber es sind gleichzeitig Komplementaritätsprobleme zu lösen, die auf dem gleichen Netzwerk leben, um die ökonomischen Gleichgewichtsbedingungen zu berücksichtigen. Frau Fischer stellt eine Reihe neuer Modelle für Konkurrenzstandortsprobleme dieser Art auf und zeigt, wie man die entstehenden Probleme lösen kann