Fast Parallel Hierarchical Aggregation/Disaggregation Algorithms for Multistage Optimization Problems and Shortest Path Problems

It appears that all of the known algorithms for solving multistage optimization problems are based explicitly on standard dynamic programming concepts. Such algorithms are inherently serial in the sense that computation must be completed at the current stage before meaningful computation can begin at the next stage. In this paper we present a technique which recursively divides the original problem into a set of smaller problems which can be solved in parallel. This technique is based on a hierarchical (recursive) structure of aggregation and disaggregation. For a multistage process with n stages, we show that our new algorithm achieves a time complexity of O(log n), assuming O(1) states per stage. However, algorithms based only on the standard dynamic programming technique can achieve a time complexity no better than O(n). Our new algorithm is designed to operate on tightly coupled parallel computer. As some important applications, it is shown that our algorithm can serve as a fast and efficient means of decoding convolutional codes, solving routing problems in data networks, and determining minimum-fuel flight paths.