C. Bonitz:

"An incremental dynamic programming approach for multidimensional allocation problems";

Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2008; final examination: 2008-05.

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.

Created from the Publication Database of the Vienna University of Technology.