Abstract

We discuss a novel approach for dealing with single-stage stochastic constraint satisfaction prob-lems (SCSPs) that include random variables over a continuous or large discrete support. Our approach is based on two novel tools: sampled SCSPs and(α, θ)-solutions. Instead of explicitly enumerating a very large or infinite set of future scenarios, we employ statistical estimation to determine if a given assignment is consistent for a SCSP. As in statisti-cal estimation, the quality of our estimate is deter-mined via confidence interval analysis. In contrast to existing approaches based on sampling, we pro-vide likelihood guarantees for the quality of the so-lutions found. Our approach can be used in concert with existing strategies for solving SCSPs