A dynamic programming approach for constrained multi-stage problems via multi-parametric programming

This paper presents a new algorithm for multi-stage decision problems with hard constraints. The algorithm is based upon the concepts of dynamic programming and multi-parametric programming. The multi-stage problem is considered within a framework of dynamic programming where each echelon of problem is formulated and solved as a multi-parametric program. The state-space of a given stage constitutes the parametric space whereas the state-space of the next stage represents the space of control or optimisation variables. The solution of the resulting multi-parametric program is given by the control or the optimization variables as a set of explicit functions of the parameters. The dynamic recursive nature of the multi-stage problem is preserved and a set of sequential and simpler multi-parametric programs which are constrained by a reduced number of inequalities is obtained. This results in a reduction in the complexity of the overall problem. The underlying theory is described in detail and numerical examples are presented to illustrate the potential of this new approach.