Efficient constraint reduction in multistage stochastic programming problems with endogenous uncertainty
Efficient constraint reduction in multistage stochastic programming problems with endogenous uncertainty
复制标题
具有内生不确定性的多阶段随机规划问题的有效约束减少
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. A. MirHassani
中科院分区：
文献类型：
--
作者：
F. Hooshmand;S. A. MirHassani
具有内生不确定性的多阶段随机规划是一个新的课题，其中不确定性的实现时间依赖于决策。在这种情况下，nonanticipativity约束（NAC）的数量增加非常迅速的情况下，使问题的计算棘手。幸运的是，大量的NAC通常是冗余的，它们的消除导致了问题规模的显著减少。识别冗余的NACs已在文献中讨论，只有在特殊情况下，场景集等于笛卡尔产品的所有可能的结果的内源性参数，但是，这是一个罕见的条件在实践中。在本文中，我们考虑的情况下，场景集是一个任意的集合，并提出了两种方法，能够识别所有冗余的NAC。第一种方法是通过混合整数规划公式和第二个是一个精确的多项式时间算法。证明了该算法能够最大限度地减少网络接入控制器的数目，这是本文的另一个新奇。计算结果评估所提出的方法的效率。
Multistage stochastic programming with endogenous uncertainty is a new topic in which the timing of uncertainty realization is decision-dependent. In this case, the number of nonanticipativity constraints (NACs) increases very quickly with the number of scenarios, making the problem computationally intractable. Fortunately, a large number of NACs are typically redundant and their elimination leads to a considerable reduction in the problem size. Identifying redundant NACs has been addressed in the literature only in the special case where the scenario set is equal to the Cartesian product of all possible outcomes for endogenous parameters; however, this is a scarce condition in practice. In this paper, we consider the general case where the scenario set is an arbitrary set; and two approaches, able to identify all redundant NACs, are proposed. The first approach is by mixed integer programming formulation and the second one is an exact polynomial time algorithm. Proving the fact that the proposed algorithm is able to make the uppermost reduction in the number of NACs is another novelty of this paper. Computational results evaluate the efficiency of the proposed approaches.