Framework for large-scale dynamic programming with applications

Dynamic Programming (DP) as coined by Bellman (1957) rests on a very simple principle "Principle of Optimality". Simply put, this principle suggests that an optimal solution can be constructed by sequentially piecing optimal sub-solutions. The key idea of DP is to use value functions to organize and structure the search for good policies. Unfortunately, there is a practical limitation in solving practical DP problems optimally because of Bellman's 'curse of dimensionality'. This 'curse of dimensionality' leads to exponential increase in time and memory to compute a solution to a DP problem as the dimension (states and control variables) increases. This thesis presents a framework to circumvent the curse of dimensionality and approximate a DP solution through an improved choice of solution algorithm along with exploitation of problem structure.; We begin by introducing value function in DP and propose framework for value function approximation. This approximation framework is based on combining sampling, local search and partitioning. To estimate the deviance of the best known feasible solution thus obtained, we propose probabilistic approaches to estimate the true optimum and its intervals.; For multicriteria DP, we propose a sampling and partitioning framework that is based on the principle of finding a representation of the true Pareto Front. We introduce new sampling concepts to estimate the ideal (nadir) point.; We apply these frameworks to solve large-scale practical optimization problems such as dynamic worker-task assignment problem, asymmetric traveling salesman problem and multidimensional knapsack problem. We compare our results with the results obtained from best-known algorithms proposed for these problems. Our results indicate that we are able to improve computational efficiency without significant reduction in solution quality.; Our framework is competitive compared to other prominent methods and produces better results in most problem instances. Our proposed framework is best suited for large-scale dynamic optimization problems with separable functions and complex constraints.