A multistage linear programming approach, which is a repeated application of Dantzig-Wolfe decomposition principle, to linear discrete-time optimal control problems with distributed-lags and state and control constraints provides an effective computational method.
Key Word Index~omputational methods; (decomposition); difference equations; discrete-time systems; (distributed-lags); linear programming; linear systems; optimal control; (state and control constraints); time lag systems; traffic control. Summary--A multistage decomposition scheme is developed for optimizing discrete-time dynamic systems, which include distributed and/or multiple pure delays. The discrete optimal control problem in this paper consists of a system dynamics described by a multidimensional linear difference equation of high-order which is called the distributed-lag model, a linear objective function, and linear state and control constraints. This problem may be solved as a linear program by, for example, a revised simplex method. However, this leads to excessive storage requirement for large problems. Instead, by taking advantage of the staircase-structure of equality constraints (system equation), Dantzig-Wolfe decomposition principle is applied repeatedly in each stage, and an effective multistage decomposition algorithm for distributed-lag models is obtained. Significant advantage of the optimization technique in this paper is that it can handle any number of delay terms in the system without reducing the multidimensional high-order system equation to a conventional larger dimensionalfirst-order system equation (state equation of normal form). Therefore, a substantial reduction of computational burden, the so called curse ofdimensionality, in the existing discrete optimal control algorithms, is obtained. A numerical example of a congested urban road traffic control problem with many delays is included.