Optimal procedures for dynamic programs with complex loop structures (Q1821703)

This paper presents an optimization procedure and the associated complexity analyses for nonserial dynamic programs involving various types of loop structures. Although in general the optimization of single loop systems requires two-dimensional memory space, we prove that under the assumption of linear transition and return functions, the processing of the main serial chain can be reduced to a one-dimensional optimization problem. For more complex structures, we consider dependent and independent multi-loop systems. Although dependent systems create a rapid increase in the complexity of algorithms, we accomplish a dramatic reduction in dimensionality by investigating the optimal absorption stage for the combined loop return. For interactive loops we introduce a node partitioning type algorithm.