Stochastic Lipschitz dynamic programming
- PDF / 980,983 Bytes
- 39 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 203 Views
Series A
Stochastic Lipschitz dynamic programming Shabbir Ahmed1 · Filipe Goulart Cabral2 · Bernardo Freitas Paulo da Costa3 Received: 21 May 2019 / Accepted: 18 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract 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 Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does not change the class of the original stochastic optimization problem. We illustrate the application of this algorithm on two case studies, comparing our approach with the convex relaxation of the problems, for which we can apply SDDP, and for a discretized approximation, applying SDDiP. Keywords Stochastic optimization · Mixed-integer optimization · Lipschitz cuts · Augmented Lagrangian duality Mathematics Subject Classification 90C15 · 90C11 · 90C26 · 90C39
Shabbir Ahmed passed away on 19 June 2019. The research of Shabbir Ahmed has been supported in part by the National Science Foundation Grant 1633196 and the Office of Naval Research Grant N00014-18-1-2075. The research of Bernardo Freitas Paulo da Costa has been supported in part by the COPPETec project IM-21780.
B
Bernardo Freitas Paulo da Costa [email protected] Shabbir Ahmed [email protected] Filipe Goulart Cabral [email protected]
1
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA
2
Operador Nacional do Sistema Elétrico, Rua Júlio do Carmo 251, Cidade Nova, Rio de Janeiro, RJ, Brazil
3
Instituto de Matemática, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil
123
S. Ahmed et al.
1 Introduction Non-convex stochastic programming problems arise naturally in models that consider binary or integer variables, since such variables allow the representation of a wide variety of constraints at the cost of inducing non-convex feasible sets. Applications such as unit commitment [1,10,21,37], optimal investment decisions [7,36], and power system operational planning [6,18,39] have driven the development of new algorithms for problems that do not fit into the convex optimization framework. For convex stochastic optimization problems, the theory and algorithms available are well-established, as can be seen for instance in reference books such as [4] and [34]. If there are not too many scenarios, one can consider the deterministic equivalent formulation, which includes all decision variables in a single convex optimization problem, that will be solved for optimality using a standard off-the-shelf solver. However, as the number of scenarios increases, the problem becomes t
Data Loading...
