This work addresses the topic of constrained dynamic programming for problems involving multi-stage mixed-integer linear formulations with a linear objective function. It is shown that such problems may be decomposed into a series of multi-parametric mixed-integer linear problems, of lower dimensionality, that are sequentially solved to obtain the globally optimal solution of the original problem. At each stage, the dynamic programming recursion is reformulated as a convex multi-parametric programming problem, therefore avoiding the need for global optimisation that usually arises in hard constrained problems. The proposed methodology is applied to a problem of mixed-integer linear nature that arises in the context of inventory scheduling. The example also highlights how the complexity of the original problem is reduced by using dynamic programming and multi-parametric programming
Multi-stage decision processes occur in different fields of study, such as energy planning (Pereira and Pinto, 1991), computational finance (Seydel, 2012), computer science (Leiserson et al., 2001), or optimal control (Bertsekas, 1995).
Dynamic programming (Bellman, 1957, Powell, 2007 and Sniedovich, 2010) is an optimisation theory used to efficiently obtain optimal solutions for problems involving multi-stage decision processes. In industrial applications, dynamic programming has been used to address problems related to project scheduling (Choi et al., 2004 and Herroelen and Leus, 2005), optimal control (Dadebo and McAuley, 1995 and Bertsekas, 1995) or robust control (Nilim and El Ghaoui, 2005 and Kouramas et al., 2012).
The method is based on the principle of optimality, and aims to reduce the complexity of conventional optimisation techniques, by exploring the sequential structure inherent to multi-stage optimisation problems. Given this structure, a suitable recursion is formulated, and the original problem disassembles into a set of sub-problems of lower dimensionality that may be solved sequentially. The dynamic programming recursion preserves the information regarding the impact of current decisions in future stages, while reducing the computational effort required to solve the overall problem.
Despite the advantages of using dynamic programming for multi-stage decision processes, its use is limited in the presence of hard constraints. In this case, at each stage of the dynamic programming recursion, non-linear decisions result and global optimisation procedures are required to solve the dynamic programming problem (Faísca et al., 2008). Another important challenge in constrained dynamic programming is that the computation and storage requirements significantly increase in the presence of hard constraints (Bertsekas, 1995).
To address these issues, different algorithms for constrained dynamic programming have been proposed, combining the principle of optimality of Bellman (1957) and multi-parametric programming techniques (Dua and Pistikopoulos, 2000 and Bemporad et al., 2002). By combining these techniques with the principle of optimality, the issues that arise for hard constrained problems are handled in a systematic way, and the shortcomings of conventional dynamic programming techniques are avoided. This method has been used to address constrained dynamic programming problems involving linear/quadratic models (Borrelli et al., 2005 and Faísca et al., 2008), and mixed-integer linear/quadratic models (Borrelli et al., 2005). However, as noted by Faísca et al. (2008), the latter involves a reformulation that produces non-convex cost functions, and therefore global optimisation techniques are required.
The proposed work extends the approach of Faísca et al. (2008) to constrained dynamic problems involving mixed-integer formulations with linear objective function and linear constraints. The proposed algorithm involves reformulating the dynamic programming recursion as a mixed-integer linear problem. At each iteration of the recursion, the original problem is relaxed by only considering the set of constraints related to the current stage. Furthermore, by taking the discrete and continuous decision variables as the optimisation vector, and the current state and future optimisation variables as parameters, the cost function of the stage is convex and the need for global optimisation techniques is avoided.
The paper is organised as follows. Section 2 presents the background on dynamic programming and shows how the corresponding recursion may be formulated as a multi-parametric mixed-integer problem, when the system is described by linear dynamics and linear constraints. It also describes a solver suitable for multi-parametric mixed integer linear problems, and the properties of the solution obtained by multi-parametric programming. The material in this section serves as the basis for the algorithm for constrained dynamic programming of mixed-integer linear systems presented in Section 3. Section 4 presents a numeric example, in which the proposed algorithm is applied to an inventory scheduling problem. Qualitative considerations regarding the complexity of this algorithm, compared to conventional multi-parametric programming, are also presented in Section 4, while the overall conclusions of the work are summarised in Section 5.
