Themenfeld B.4: Online-Algorithmen zum Optimieren in der Forst- und Agrarwirtschaft

Gerade in Bezug auf die Unsicherheiten, die im Rahmen der forst- und agrarwirtschaftlichen Anwendungen zu berücksichtigen sind, müssen in der Praxis oft Entscheidungen getroffen werden, ohne dass alle dafür relevanten Daten (Schädlingsbefall, Wetterbedingungen des kommenden Jahres, Marktpreise,…) bereits zur Verfügung stehen. Die Online-Optimierung (Albers, 2010) befasst sich mit der Frage, wie gut Planung unter Unsicherheit, insbesondere ohne das Vorliegen einer endgültigen Datengrundlage, sein kann und sucht nach Algorithmen, die in diesem Umfeld bestmögliche Ergebnisse erzielen. Man bezeichnet Algorithmen, die solche Entscheidungen ohne vollständiges Wissen aller Eingabedaten fällen, als Online-Algorithmen. Entsprechend wird ein Algorithmus, der über all diese Informationen von Anfang an verfügt, Offline-Algorithmus genannt. Zur Beurteilung der Lösungsqualität von Online-Algorithmen hat sich die Kompetitive Analyse (Borodin, El-Yaniv, 1998) etabliert, die das Ergebnis eines Online-Algorithmus mit dem Ergebnis eines optimalen Offline-Algorithmus vergleicht.

In diesem Themenfeld werden Online-Algorithmen für Planungsprobleme, die aus der Informationsunsicherheit entlang der Produktions- und Wertschöpfungsketten in gegebenen Unternehmensnetzwerken resultieren, entwickelt und Aussagen über deren Lösungsqualität getroffen. Außerdem werden sinnvolle Annahmen über die unbekannten Daten gemacht und die Qualität der Algorithmen in Bezug zu diesen gesetzt. Bei der Formulierung der zu betrachtenden Online-Probleme und der Abschätzung der zugrundeliegenden Wahrscheinlichkeitsverteilungen wird auf Zwischenresultate und Ergebnisse der Dissertationen aus der Themengruppe A, und dort vor allen aus dem Themenfeld A.1 zurückgegriffen. Auch das Themenfeld B.2 kann wichtigen Input liefern. Der Unterschied zur in Themenfeld B.3 behandelten robusten Optimierung liegt darin, dass bei dieser in einer ersten Phase Entscheidungen getroffen werden müssen, die für alle denkbaren Entwicklungen, die in einer zweiten Phase stattfinden, zulässig bleiben. Ein Online-Algorithmus hingegen arbeitet eine Sequenz von Anfragen ab (z.B. Angebote eines potenziellen Auftragnehmers) und trifft jeweils eine Entscheidung (z.B. Annehmen oder Ablehnen). Der neue Ansatz der „Recoverable Robustness“ (Cicerone et al., 2008) schafft eine konzeptuelle Schnittstelle zwischen den beiden Themenbereichen. Wegen der thematischen Verwandtschaft kann im Rahmen der Arbeiten dieses Themenfeldes untersucht werden, inwieweit sich die für diese unterschiedlichen Unsicherheitskonzepte entwickelten Verfahren jeweils auf das andere Themenfeld übertragen lassen. Die in dieser Arbeit entwickelten Verfahren können im Gegenzug als Input für die Themenfelder B.1, B.2 und B.6 verwendet werden.

Zur Behandlung des vorliegenden Themenkomplexes werden Methoden der diskreten Optimierung verwendet. Zunächst werden die entsprechenden Offline-Probleme formuliert und untersucht. Daraufhin werden sowohl deterministische als auch randomisierte Online-Algorithmen entwickelt und deren Kompetitivität abgeschätzt sowie allgemeine Aussagen bezüglich der bestmöglichen Qualität von Online-Algorithmen in diesem Umfeld getroffen (z.B. durch Yao’s Prinzip (Yao, 1977)). Dabei wird unter anderem auf Methoden der linearen Optimierung, der ganzzahligen Optimierung und der Netzwerkoptimierung zurückgegriffen, um sowohl exakte als auch heuristische Verfahren zu entwickeln und ihre Qualität zu beurteilen. Außerdem wird die Anwendbarkeit der entwickelten Verfahren durch Simulationen getestet, um eine Einschätzung des Average-Case-Verhaltens der Algorithmen zu erlangen