[Zurück]

C. Bonitz:
"An incremental dynamic programming approach for multidimensional allocation problems";
Betreuer/in(nen): G. Raidl; Institut für Computergraphik und Algorithmen, 2008; Abschlussprüfung: 05/2008.

This thesis presents an incremental Dynamic Programming (DP) Ap-
proach 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 e ciently store large amounts
of energy. To achieve good pro ts, it is necessary to plan when to use this
energy to generate electricity.
The formal problem addressed in this thesis is nding an optimal pol-
icy for allocating a good, for example water, represented in discrete units,
from several stores with limited capacity over a nite period of time (rep-
resented 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 di er only
by one unit in the capacity of a single store have optimal solutions that
lie within a de ned neighborhood of each other. This neighborhood can
e ciently be searched by Dynamic Programming.
An algorithm is presented that uses this property to nd an opti-
mal 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 algo-
rithm, Optimal Policy Iteration, is compared with a standard Dynamic
Programming approach as well as an Evolutionary Algorithm.
The algorithm performs signi cantly 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 counterex-
ample shows that the uncertainty about future prices makes it impossible
to directly translate the locality results from deterministic pricing to a
price scenario.