Abstract
In this paper, we propose a novel notion of statistical consistency for single-stage Stochastic Constraint Satisfaction Problems (SCSPs) in which some of the random variables’ support set is infinite. The essence of this novel notion of local consistency is to be able to make an inference in the presence of infinite scenarios in an uncertain environment. This inference would be based on a restricted finite subset of scenarios with a certain confidence level and a threshold tolerance error. The confidence level is the probability that characterizes the extend to which our inference — based on a subset of scenarios — is correct. The threshold tolerance error is the error range that we can tolerate while making such an inference. We propose a novel statistical consistency enforcing algorithm that is based on sound statistical inference; and experimentally show how to prune inconsistent values in the presence of an infinite set of scenarios.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Change history
05 May 2018
The original version of this article unfortunately contained a mistake. The name “Abdelwahad Rebaii” should be corrected to “Abdelwaheb Rebai”.
References
Agresti, A., Coull, B.A.: Approximate is better than “exact” for interval estimation of binomial proportions. Am. Stat. 52(2), 119–126 (1998)
Apt, K.: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)
Beck, J.C., Wilson, N.: Proactive algorithms for job shop scheduling with probabilistic durations. J. Artif Intell. Res. (JAIR) 28, 183–232 (2007)
Benoist, T., Bourreau, E., Caseau, Y., Rottembourg, B.: Towards stochastic constraint programming: a study of online multi-choice knapsack with deadlines. In: Walsh, T. (ed.) CP 2001, Proceedings, volume 2239 of LNCS, pp. 61–76. Springer (2001)
Clopper, C., Pearson, E.: The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika 26(4), 404–413 (1934)
Green, S.B., Babyak, M.A.: Control of type i errors with multiple tests of constraints in structural equation modeling. Multivar. Behav. Res. 32(1), 39–51 (1997)
Van Hentenryck, P., Bent, R., Vergados, Y.: Online stochastic reservation systems. In: Beck, J.C., Smith, B.M. (eds.) CPAIOR 2006, Cork, Ireland, May 31 - June 2 Christopher Proceedings, volume 3990 of Lecture Notes in Computer Science, pp. 212–227. Springer (2006)
Hnich, B., Rossi, R., Armagan, T.S., Prestwich, S.D.: Filtering algorithms for global chance constraints. Artif. Intell. 189, 69–94 (2012)
Kleywegt, A.J., Shapiro, A., Homem-De-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479–502 (2001)
Papoulis, A.: Probability, Random Variables and Stochastic Processes, 2nd ed. McGraw-Hill, New York (1984)
R Core Team: R: a language amd Environment for Statistical Computing R Foundation for Statistical Computing (2013)
Rossi, R., Hnich, B., Armagan Tarim, S., Prestwich, S.: Confidence-based reasoning in stochastic constraint programming. Artif. Intell. 228, 129–152 (2015)
Rossi, R., Hnich, B., Armagan Tarim, S., Prestwich, Steven David: Finding (α,𝜗)-solutions via sampled Scsps. In: IJCAI, pp. 2172–2177 (2011)
Rossi, R., Prestwich, S., Armagan Tarim, S., Hnich, B.: Confidence-based optimisation for the newsvendor problem under binomial, poisson and exponential demand European Journal of Operational Research (2014)
Tarim, S.A., Manandhar, S., Walsh, T.: Stochastic constraint programming: a scenario-based approach. Constraints 11(1), 53–80 (2006)
Vollset, S.E.: Confidence intervals for a binomial proportion. Stat. Med. 12(9), 809–824 (1993)
Walsh, T.: Stochastic Constraint Programming. In: Proceedings of the ECAI’2002, pp. 111–115 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
The original version of this article was revised: The name “Abdelwahad Rebaii” should be corrected to “Abdelwaheb Rebai”. The correct name is now shown here.
Rights and permissions
About this article
Cite this article
Zghidi, I., Hnich, B. & Rebai, A. Introducing statistical consistency for infinite chance constraints. Ann Math Artif Intell 83, 165–181 (2018). https://doi.org/10.1007/s10472-018-9572-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-018-9572-3