Approximate solution techniques for acyclic deterministic dynamic programming.

Dynamic programming is a general technique to formulate problems which involve a sequence of decisions made to optimize a given performance criterion. Using this technique we are able to capture important rough terrain properties that are precluded within the standard mathematical programming model. However, the size of the resulting formulation and in particular the size of the state space can make solving the problem computationally prohibitive. To address this problem, we have developed and refined several approximate solution techniques. We propose and analyze a heuristic algorithm based on state pruning which successively eliminates solutions. At each step it is guaranteed that the remaining solution set has a solution within an a priori error from the optimal. We illustrate using dynamic programming with guaranteed error bounds on a problem in single location capacity expansion. In addition, we introduce an aggregation technique which utilizes a nested hierarchy of aggregate levels to reduce the computational burden of the original problem's state space. We provide an algorithm which simultaneously creates the nested aggregate networks and solves for a near optimal solution in the original network. A computable error bound from optimality is provided. A generic aggregation scheme technique was developed by Bean, Birge, and Smith. However, the effectiveness of this technique is dependent on the given aggregation scheme. We have developed a dynamic programming based technique to create an aggregation scheme in an attempt to minimize the error of the resulting disaggregated solution, while still reaping the potential computational benefits of aggregation. This technique is investigated and refined to provide the building blocks for future generic aggregation scheme generation.Ph.D.Applied SciencesIndustrial engineeringOperations researchUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/129089/2/3042037.pd