Bernardo Freitas Paulo da Costa For multistage stochastic programming problems with stagewise independent uncertainty, dynamic programming algorithms calculate polyhedral approximations for the value functions at each stage. The SDDP algorithm provides piecewise linear lower bounds, in the spirit of the L-shaped algorithm, and corresponding upper bounds took a longer time to appear. One strategy uses the primal dynamic programming recursion … Read more
Risk-averse multistage stochastic programs appear in multiple areas and are challenging to solve. Stochastic Dual Dynamic Programming (SDDP) is a well-known tool to address such problems under time-independence assumptions. We show how to derive a dual formulation for these problems and apply an SDDP algorithm, leading to converging and deterministic upper bounds for risk-averse problems. … Read more
We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost to go functions. An example of such a class of cuts are those derived using … Read more