Stochastic dual dynamic integer programming
Stochastic dual dynamic integer programming
复制标题
DOI：
10.1007/s10107-018-1249-5
复制
发表时间：
2018-03
影响因子：
2.7
通讯作者：
Jikai Zou;Shabbir Ahmed;X. Sun
中科院分区：
文献类型：
--
作者：
Jikai Zou;Shabbir Ahmed;X. Sun
多阶段随机整数规划（MSIP）结合了不确定性、动态性和非凸性的困难，构成了一类极具挑战性的问题。这些问题的一个常见的公式是一个动态规划公式，涉及嵌套的成本去功能。在线性环境下，剩余成本函数是凸多面体，分解算法，如嵌套Benders分解及其随机变体，随机对偶动态规划（SDDP），通过截集或线性不等式迭代逼近这些函数，已被建立为有效的方法。然而，由于整数规划值函数的非凸性，很难直接将这些算法应用于MSIP。在本文中，我们提出了一个扩展SDDP-称为随机对偶动态整数规划（SDDiP）-解决MSIP问题的二元状态变量。该算法的关键组成部分是一个新的重新制定的子问题，在每个阶段和一个新的类的削减，称为拉格朗日削减，来自拉格朗日松弛的一个特定的重新制定的子问题，在每个阶段，其中引入了本地副本的状态变量。我们证明了拉格朗日切割满足一个紧性条件，并提供了严格的证明有限收敛的SDDiP的概率为1。我们表明，在相当合理的假设下，一般状态变量的MSIP问题可以近似为一个二进制状态变量所需的精度，只有适度增加问题的大小。因此，我们提出的SDDiP方法适用于非常一般的类MSIP问题。大量的计算实验三类现实世界的问题，即发电扩展，金融投资组合管理，网络收益管理，表明所提出的方法是非常有效的，在解决大规模的多阶段随机整数优化问题。
Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and its stochastic variant, stochastic dual dynamic programming (SDDP), which proceed by iteratively approximating these functions by cuts or linear inequalities, have been established as effective approaches. However, it is difficult to directly adapt these algorithms to MSIP due to the nonconvexity of integer programming value functions. In this paper we propose an extension to SDDP—called stochastic dual dynamic integer programming (SDDiP)—for solving MSIP problems with binary state variables. The crucial component of the algorithm is a new reformulation of the subproblems in each stage and a new class of cuts, termed Lagrangian cuts, derived from a Lagrangian relaxation of a specific reformulation of the subproblems in each stage, where local copies of state variables are introduced. We show that the Lagrangian cuts satisfy a tightness condition and provide a rigorous proof of the finite convergence of SDDiP with probability one. We show that, under fairly reasonable assumptions, an MSIP problem with general state variables can be approximated by one with binary state variables to desired precision with only a modest increase in problem size. Thus our proposed SDDiP approach is applicable to very general classes of MSIP problems. Extensive computational experiments on three classes of real-world problems, namely electric generation expansion, financial portfolio management, and network revenue management, show that the proposed methodology is very effective in solving large-scale multistage stochastic integer optimization problems.