Solving Stochastic Two-Stage Programs with Fixed Recourse: The Dual-Clustering Constraint-Generation Approach

Two-stage stochastic programming provides a standard framework for decision-making under uncertainty when here-and-now choices precede random revelations and a fixed-recourse policy follows. With large finite scenario sets and risk aversion, the expected recourse cost is commonly replaced by Conditional Value-at-Risk (CVaR). To solve the ensuing large deterministic equivalents efficiently, we propose a single-loop algorithm that (i) performs dual clustering, grouping scenarios that share the same optimal second-stage dual solution, and (ii) uses constraint generation, adding only the hyperplanes required to represent CVaR. Convergence holds under mild conditions and the algorithm stops once the reduced-model CVaR matches, within tolerance, the value computed on the full scenario set. Our method strengthens existing clustering-and-constraint-generation approaches for fixed-recourse problems by adopting partition-based refinement rules known in the literature, and it is complementary to Benders adaptive-cuts ideas. In computational tests we tackle the Stochastic Facility Location Problem under risk aversion (CVaR), running multiple experiments built from the classic capacitated warehouse location instances in the OR-Library, and we compare directly against a Benders adaptive-cuts methodology and others. The proposed approach attains the same reliability as the full model at a fraction of the computing time, achieving speed-ups of one to more than three orders of magnitude while preserving fixed-recourse structure.