Bonitz, C. (2008). An incremental Dynamic Programming Approach for multidimensional allocation problems [Master Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/183777
Diese Arbeit präsentiert einen Algorithmus zur Lösung eines Optimierungsproblems. Das Problem ist inspiriert von der Planung der Energieerzeugung in Wasserspeicherkraftwerken. In Wasserspeicherkraftwerken können große Mengen von Energie effizient gespeichert, und gezielt bei hohen Strompreisen in Elektrizität umgesetzt werden. Im in dieser Arbeit behandelten formalen Problem versuchen wir ein durch diskrete Einheiten repräsentiertes Gut, zum Beispiel Wasser, aus mehreren Speichern über eine beschränkte Planungperiode (repräsentiert durch "Entscheidungspunke") optimal zu verteilen, wobei Beschränkungen über die Gesamtzahl der Allokationen aus allen Speichern pro Zeitschitt möglich sind. Der Zielfunktionswert modelliert einen erwarteten Marktpreis und ist die Summe von konkaven Preisfunktionen. Wir können zeigen, dass durch die konkaven Preisfunktionen die Optimallösungen von zwei Probleminstanzen, die sich nur um eine Einheit in der Kapazität eines einzigen Speichers unterscheiden, die Optimallösungen in einer definierten Nachbarschaft befinden, die effektiv mit Dynamischer Programmierung durchsucht werden kann. Ein Algorithmus namens Optimal Policy Iteration (OPI) wird präsentiert, der diese Eigenschaft nutzt um die Optimallösung zu einer gegebenen Probleminstanz, ausgehend von der Optimallösung einer trivialen Instanz, iterativ über eine Reihe von optimalen Lösungen für "wachsende" Probleminstanzen zu finden. Der Algorithmus wird verglichen mit einem einfacheren Dynamische Programmierung-Verfahren sowie einem Evolutionären Algorithmus. Die Laufzeiten von OPI sind erheblich kürzer als die des einfachen Dynamische Programmierung-Algorithmus. Der Evolutionäre Algorithmus ist bei mehr Dimensionen schneller, garantiert aber keine Optimalität. Ein theoretisches Resultat dieser Arbeit ist, dass OPI in der aktuellen Form nicht einfach erweitert werden kann, um Preisszenarien zu berücksichtigen, da die Nachbarschaftseigenschaft nicht erhalten bleibt.
This thesis presents an incremental Dynamic Programming (DP) Approach called Optimal Policy Iteration for solving an allocation problem inspired by Hydro Storage System Planning. Hydroelectric power plants have the unique property of being able to efficiently store large amounts of energy. To achieve good profits, it is necessary to plan when to use this energy to generate electricity. The formal problem addressed in this thesis is finding an optimal policy for allocating a good, for example water, represented in discrete units, from several stores with limited capacity over a finite period of time (represented by discrete decision points). The number of allocations can be constrained for each time step as well as for each combination of store and time step. The objective value models the expected development of the good's market price, and is computed as the sum of concave functions of the decision variables called pricing functions. It is shown that, because of the concave pricing functions, two problem instances that are identical with respect to allocation limits and differ only by one unit in the capacity of a single store have optimal solutions that lie within a defined neighborhood of each other. This neighborhood can efficiently be searched by Dynamic Programming. An algorithm is presented that uses this property to find an optimal policy for a given problem instance using a series of optimal policies for sub-problem-instances that are ``growing'' with respect to capacities, starting with the optimal solution to a trivial sub-problem. This algorithm, Optimal Policy Iteration, is compared with a standard Dynamic Programming approach as well as an Evolutionary Algorithm. The algorithm performs significantly better than a simple DP solution, making it possible to solve problem instances with large capacities. The evolutionary algorithm performs better on instances with many stores, but is not guaranteed to give optimal solutions. The algorithm uses a deterministic pricing scheme. In its current form it cannot simply be extended to stochastic pricing models. A counterexample shows that the uncertainty about future prices makes it impossible to directly translate the locality results from deterministic pricing to a price scenario.