Constrained dynamic programming of mixed-integer linear problems by multi-parametric programming

doi:10.1016/j.compchemeng.2014.03.021

Return

Constrained dynamic programming of mixed-integer linear problems by multi-parametric programming

2014-11-01

PRE

Pedro Rivotti *

Efstratios N. Pistikopoulos

DOI：10.1016/j.compchemeng.2014.03.021

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2014 Elsevier Ltd. All rights reserved.

Keywords:

Dynamic programming

Multi-parametric programming

Mixed-integer linear programming

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.