Accelerating the solution of dynamic programs through state aggregation.

Abstract

The procedure of solving sequential decision problems by the Dynamic Programming (DP) approach can be summarized by two distinct phases. The first phase, the so-called formulation phase, involves a transformation into a DP functional equation, which usually can be viewed as an optimization problem in a Dynamic Programming Network (DPN). The second phase, the so-called solution phase, involves an efficient approach for solving for an optimal path in the resulting DPN. In this dissertation, two issues within the framework of Dynamic Programming are specifically considered. One focuses on developing the methodology for the transformation process in the formulation phase of DP, and the other focuses on establishing approaches of accelerating the solution phase. Our underlying ideas behind both developments are based on aggregation techniques. We present an approach to formulating DP function equations through a node aggregation operation. Furthermore, a regularity condition on the path cost function is presented which defines the class of problems to which the DP approach can be applied. Due to the fact that a problem usually can be formulated as a DP functional equation in more than one way and the resulting complexity may vary significantly, we further investigate the issue of the most efficient DP formulation for the classic knapsack problem. We propose a class of heuristics, called the Hierarchical Aggregation Algorithms (HAA), for accelerating the solution phase of DP through network aggregation. Since a dynamic program usually can be viewed as an shortest path problem in a directed network, these heuristics are presented as algorithms for solving shortest path problem in cyclic networks. By assuming a probabilistic model for the parameters of the network, an upper bound is derived for the error yielded by the approximate solution. A complexity analysis is also conducted to investigate the efficiency of the heuristic versus the exact approach for solving classes of shortest path problems. Finally, a numerical experiment is performed based on a real network--the Southeast Michigan road network.