Optimization Online


Dual Dynamic Programming with cut selection: convergence proof and numerical experiments

Vincent Guigues(vincent.guigues***at***gmail.com)

Abstract: We consider convex optimization problems formulated using dynamic programming equations. Such problems can be solved using the Dual Dynamic Programming 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.

Keywords: Dynamic Programming ; Nonlinear programming; Decomposition algorithms; Dual Dynamic Programming; Pruning methods

Category 1: Convex and Nonsmooth Optimization

Category 2: Other Topics (Dynamic Programming )

Citation: V. Guigues, Dual Dynamic Programing with cut selection: Convergence proof and numerical experiments, European Journal of Operational Research, 258 (1): 47-57, 2017.

Download: [PDF]

Entry Submitted: 05/24/2017
Entry Accepted: 05/24/2017
Entry Last Modified: 05/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society