Two-stage linear decision rules for multi-stage stochastic programming
Two-stage linear decision rules for multi-stage stochastic programming
复制标题
多阶段随机规划的两阶段线性决策规则
DOI：
10.1007/s10107-018-1339-4
复制
发表时间：
2018
影响因子：
2.7
通讯作者：
Luedtke, James R.
中科院分区：
文献类型：
--
作者：
Bodur, Merve;Luedtke, James R.
多阶段随机线性规划（MSLP）通常很难求解。线性决策规则（LDR）通过将每个阶段的决策限制为所观察到的不确定参数的仿射函数来产生MSLP的近似。寻找最优LDR是一个静态优化问题，它提供了MSLP最优值的上限，并且在某些假设下，可以用公式表示为显式线性规划。类似地，如Kuhn等人（Math Program 130（1）：177-209，2011）所提出的，可以通过将MSLP的对偶中的决策限制为遵循LDR来获得MSLP的下限。我们提出了一种新的近似方法MSLP，两阶段LDR。其思想是只要求MSLP中的状态变量遵循LDR，这足以获得MSLP的近似，即两阶段随机线性规划（2SLP）。同样，我们建议仅将LDR应用于MSLP的对偶中的变量的子集，这产生对偶的2SLP近似，其提供MSLP的最优值的下限。尽管准确求解相应的2SLP近似值通常很棘手，但我们研究了如何将为求解2SLP而开发的近似求解方法应用于求解这些近似问题，并推导出MSLP最优值的统计上界和下界。除了可能产生更好的政策和界限，这种方法需要少得多的假设比需要获得一个明确的重新制定时，使用标准的静态LDR方法。两个示例问题的计算研究表明，使用两阶段LDR可以产生显着更好的原始政策和适度更好的双重政策比使用基于静态LDR的政策。
Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn et al. (Math Program 130(1):177–209, 2011) a lower bound for an MSLP can be obtained by restricting decisions in the dual of the MSLP to follow an LDR. We propose a new approximation approach for MSLPs,two-stage LDRs. The idea is to require only the state variables in an MSLP to follow an LDR, which is sufficient to obtain an approximation of an MSLP that is atwo-stage stochastic linear program(2SLP). We similarly propose to apply LDR only to a subset of the variables in the dual of the MSLP, which yields a 2SLP approximation of the dual that provides a lower bound on the optimal value of the MSLP. Although solving the corresponding 2SLP approximations exactly is intractable in general, we investigate how approximate solution approaches that have been developed for solving 2SLP can be applied to solve these approximation problems, and derive statistical upper and lower bounds on the optimal value of the MSLP. In addition to potentially yielding better policies and bounds, this approach requires many fewer assumptions than are required to obtain an explicit reformulation when using the standard static LDR approach. A computational study on two example problems demonstrates that using a two-stage LDR can yield significantly better primal policies and modestly better dual policies than using policies based on a static LDR.
登录
查看更多内容
SDDP.jl：随机对偶动态规划的 Julia 包
影响因子：
2.1
作者：
O. Dowson;L. Kapelevich
通讯作者：
L. Kapelevich
随机规划的对偶性解释为 $L_p $-Space 中的 L. P.
DOI：
--
发表时间：
1975
期刊：
影响因子：
--
作者：
M. Eisner;Paul Olsen
通讯作者：
Paul Olsen
DOI：
10.1137/140983136
发表时间：
2014-08
期刊：
SIAM J. Optim.
影响因子：
--
作者：
V. Guigues
通讯作者：
V. Guigues
多级随机线性规划嵌套分解算法的并行实现
影响因子：
2.7
作者：
J. Birge;Christopher J. Donohue;Derek F. Holmes;Oleg G. Svintsitski
通讯作者：
Oleg G. Svintsitski
影响因子：
2.7
作者：
M. Koivu
通讯作者：
M. Koivu