title: Optimization of stochastic-dynamic decision problems with applications in energy and production systems
Creators: name: Löhndorf, Nils
Publisher: name: :none
Year: 2011

description: Die vorliegende Arbeit beschäftigt sich mit der mathematischen Optimierung von stochastisch-dynamischen Entscheidungsproblemen. Diese Problemklasse stellt eine besondere Herausforderung für die mathematische Optimierung dar, da bislang kein Lösungsverfahren bekannt ist, das in polynomieller Zeit zu einer exakten Lösung konvergiert. Alle generischen Verfahren der dynamischen Optimierung unterliegen dem sogenannten "Fluch der Dimensionen", der dazu führt, dass die Problemkomplexität exponentiell in der Anzahl der Zustandsvariablen zunimmt. Da Entscheidungsprobleme von realistischer Größenordnung meist über eine Vielzahl von Zustandsvariablen verfügen, stoßen exakte Lösungsverfahren schnell an ihre Grenzen. Einen vielversprechenden Ausweg, um dem Fluch der Dimensionen zu entgehen, stellen Verfahren der "approximativ-dynamischen Optimierung" dar (engl.: "approximate dynamic programming"), welche versuchen eine Nährungslösung des stochastisch-dynamischen Problems zu berechnen. Diese Verfahren erzeugen eine künstliche Stichprobe des Entscheidungsprozesses mittels Monte-Carlo-Simulation und konstruieren basierend auf dieser Stichprobe eine Approximation der Wertfunktion des dynamischen Problems. Dabei wird die Stichprobe so gewählt, dass lediglich diejenigen Zustände in die Stichprobe aufgenommen werden, welche für den Entscheidungsprozess von Bedeutung sind, wodurch eine vollständige Enumeration des Zustandsraums vermieden wird. In dieser Arbeit werden Verfahren der approximativ-dynamischen Optimierung auf verschiedene Probleme der Produktions- und Energiewirtschaft angewendet und daraufhin überprüft, ob sie in der Lage sind, das zugrundeliegende mathematische Optimierungproblem nährungsweise zu lösen. Die Arbeit kommt zu dem Ergebnis, dass sich komplexe stochastisch-dynamische Bewirtschaftungsprobleme effizient lösen lassen, sofern das Optimierungsproblem konvex und der Zufallsprozess unabhängig vom Entscheidungsprozess ist. Handelt es sich hingegen um ein diskretes Optimierungsproblem, so stoßen auch Verfahren der approximativ-dynamischen Optimierung an ihre Grenzen. In diesem Fall sind gut kalibrierte, einfache Entscheidungsregeln möglicherweise die bessere Alternative.
description: This thesis studies mathematical optimization methods for stochastic-dynamic decision problems. This problem class is particularly challenging, as there still exists no algorithm that converges to an exact solution in polynomial time. Existing generic solution methods are all subject to the "curse of dimensionality", which means that problem complexity increases exponentially in the number of state variables. Since problems of realistic size typically come with a large number of state variables, applying exact solution methods is impractical. A promising methodology to break the curse of dimensionality is "approximate dynamic programming". To avoid a complete enumeration of the state space, solution techniques based on this methodology use Monte Carlo simulation to sample states that are relevant to the decision process and then approximate the value function of the dynamic program by a function of much lower complexity. This thesis applies approximate dynamic programming techniques to different resource management problems that arise in production and energy settings and studies whether these techniques are capable of solving the underlying optimization problems. The thesis concludes that stochastic-dynamic resource management problems can be solved efficiently if the underlying optimization problem is convex and randomness independent of the resource states. If the optimization problem is discrete, however, the problem remains hard to solve, even for approximate dynamic programming techniques. In this case, simple but well-adjusted decision policies may be the better choice.