Dual Dynamic Programing with cut selectionconvergence proof and numerical experiments

Resumo

We consider convex optimization problems formulated using dynamic programing equations. Such problems can be solved using the Dual Dynamic Programing algorithm combined with the Level 1 cut selection strategy or the Territory algorithm to select the most relevant Benders cuts. We propose a limited memory variant of Level 1 and show the convergence of DDP combined with the Territory algorithm, Level 1 or its variant for nonlinear optimization problems. In the special case of linear programs, we show convergence in a finite number of iterations. Numerical simulations illustrate the interest of our variant and show that it can be much quicker than a simplex algorithm on some large instances of portfolio selection and inventory problems. (C) 2016 Elsevier B.V. All rights reserved.

Ficha do documento

Tipo

Artigo científico

Ano

2017

Instituição

Elsevier Science Bv

Fonte

Repositório da FGV

Idioma

Inglês

Acesso

Acesso restrito

DOI

10.1016/j.ejor.2016.10.047

Identificador

oai:repositorio.fgv.br:10438/23696

Palavras-chave

Dynamic programingNonlinear programingDecomposition algorithmsDual Dynamic ProgramingPruning methodsAdministração de empresasTeorias não-linearesAlgoritmos