A Successive Refinement for Solving Stochastic Programs with Decision-Dependent Random Capacities

Article Status: Under Review
Publication Year: 2024
Hugh Medal and Samuel Affar.
[PDF]  [Slides]

We study a class of two-stage stochastic programs in which the second stage includes

a set of components with uncertain capacity, and the expression for the distribution function

of the uncertain capacity includes first-stage variables. Thus, this class of problems has the

characteristics of a stochastic program with decision-dependent uncertainty. A natural way to

formulate this class of problems is to enumerate the scenarios and express the probability of

each scenario as a product of the first-stage decision variables; unfortunately, this formulation

results in an intractable model with a large number of variable products with high-degree. After

identifying structural results related to upper and lower bounds and how to improve these bounds,

we present a successive refinement algorithm that successively and dynamically tightens these

bounds. Implementing the algorithm within a branch-and-cut method, we report the results of

computational experiments that indicate that the successive refinement algorithm significantly

outperforms a benchmark approach. Specifically, results show that the algorithm finds an optimal

solution before the refined state space become too large.