Solving Two-Stage Programs with Endogenous Uncertainty via Random Variable Transformation

Real-world decision-making problems often involve decision-dependent uncertainty, where the probability distribution of the random vector depends on the model’s decisions. Few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We propose a general method for solving a class of these programs based on random variable transformation, a technique widely employed in probability and statistics. The random variable transformation converts a stochastic program with endogenous uncertainty (original program) into an equivalent stochastic program with decision-independent uncertainty (transformed program), for which solution procedures are well studied. Additionally, endogenous uncertainty usually leads to nonlinear nonconvex programs, which are theoretically intractable. Nonetheless, we show that for some classical endogenous distributions, the proposed method yields mixed-integer linear or convex programs with exogenous uncertainty. We validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. Although the original formulation of this problem is nonlinear nonconvex for most endogenous distributions, the proposed method transforms it into mixed-integer linear programs with exogenous uncertainty. We solve these transformed programs with the sample average approximation method. We highlight the superior performance of our approach compared with solving the original program in the case that a mixed-integer linear formulation of this program exists.

History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.

Funding: This research was funded by Scale AI [the SCALE-AI Chair in Data-Driven Supply Chains], the Fonds de recherche du Québec [the FRQ -IVADO Research Chair], the IVADO [the FRQ -IVADO Research Chair], and the Natural Sciences and Engineering Research Council of Canada [Grant 2024-04051].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0847) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0847). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.