  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.
