论文标题
利用决策图以二进制求程和逻辑链接约束解决两个阶段的随机程序
Leveraging Decision Diagrams to Solve Two-stage Stochastic Programs with Binary Recourse and Logical Linking Constraints
论文作者
论文摘要
带有二进制追索权的两阶段随机程序在解决此类问题的解决方案方法方面具有挑战性。在这项工作中，我们概括了Lozano和Smith（Math。Program。，2018）的现有基于二进制决策图（基于BDD）的方法，以通过二进制追索方式解决一类特殊的两阶段随机程序。在这种情况下，第一阶段的决策会影响第二阶段的约束。我们修改的问题将第二阶段的问题扩展到了更通用的设置，其中第一阶段解决方案的逻辑表达式在第二阶段执行了约束。我们还提出了一种互补问题和解决方案方法，可用于许多相同的应用程序。在互补问题中，我们的第二阶段成本受到第一阶段决策的表达影响。在这两种设置中，我们都使用BDD将第二阶段问题转发，并根据问题的不同，将这些BDD的ARC成本或这些BDD的容量或能力取决于问题。我们通过纳入有条件的危险价值来进一步扩展这项工作，并据我们所知，我们建议使用二进制追索和风险度量的两阶段随机程序的第一种分解方法。我们将这些方法应用于一种新型的随机统治集合问题，并提出数值结果，以证明所提出的方法的有效性。
Two-stage stochastic programs with binary recourse are challenging to solve and efficient solution methods for such problems have been limited. In this work, we generalize an existing binary decision diagram-based (BDD-based) approach of Lozano and Smith (Math. Program., 2018) to solve a special class of two-stage stochastic programs with binary recourse. In this setting, the first-stage decisions impact the second-stage constraints. Our modified problem extends the second-stage problem to a more general setting where logical expressions of the first-stage solutions enforce constraints in the second stage. We also propose a complementary problem and solution method which can be used for many of the same applications. In the complementary problem we have second-stage costs impacted by expressions of the first-stage decisions. In both settings, we convexify the second-stage problems using BDDs and parametrize either the arc costs or capacities of these BDDs with first-stage solutions depending on the problem. We further extend this work by incorporating conditional value-at-risk and we propose, to our knowledge, the first decomposition method for two-stage stochastic programs with binary recourse and a risk measure. We apply these methods to a novel stochastic dominating set problem and present numerical results to demonstrate the effectiveness of the proposed methods.
