Nested Decomposition of Multistage Convex Programs

Abstract

The multistage or staircase structure appears naturally in many models with time horizons. This paper presents and discusses a method for decomposition when the problem functions are convex. Among the techniques which can be used to solve the subproblems are the Dantzig–Wolfe convex programming algorithm and Bender’s decomposition. Furthermore, when the nature of the problem presents certain structural forms, the decomposition allows for the introduction of more efficient techniques.