Constrained dynamic programming of mixed-integer linear problems by multi-parametric programming Academic Article uri icon


  • 2014 Elsevier Ltd. 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.

published proceedings


author list (cited authors)

  • Rivotti, P., & Pistikopoulos, E. N.

citation count

  • 14

complete list of authors

  • Rivotti, Pedro||Pistikopoulos, Efstratios N

publication date

  • November 2014