Towards statistical consistency for stochastic constraint programming

Autor: Imen Zghidi
Rok vydání: 2017
Předmět:
Zdroj: Constraints. 22:101-102
ISSN: 1572-9354
1383-7133
DOI: 10.1007/s10601-016-9264-8
Popis: In most industrial contexts, decisions are made based on incomplete information. This is due to the fact that decision makers cannot be certain of the future behavior of factors that will affect the outcome resulting from various options under consideration. Stochastic Constraint Satisfaction Problems provide a powerful modeling framework for problems in which one is required to take decisions under uncertainty. In these stochastic problems, the uncertainty is modeled by using discrete random variables to capture uncontrollable factors like the customer demands, the processing times of machines, house prices, etc. These discrete random variables can take on a set of possible different values, each with an associated probability and are useful to model factors that fall outside the control of the decision maker who only knows the probability distribution function of these random variables which can be forecasted, for instance, by looking at the past behavior of such factors. There are controllable variables on which one can decide, named decision variables which allow to model the set of possible choices for the decisions to be made. Finally, such problems comprise chance constraints which express the relationship between random and decision variables that should be satisfied within a satisfaction probability threshold --- since finding decisions that will always satisfy the constraints in an uncertain environment is almost impossible. If the random variables' support set is infinite, the number of scenarios would be infinite. Hence, finding a solution in such cases is impossible in general. In this thesis, within the context of an infinite set of scenarios, we propose a novel notion of statistical consistency. Statistical consistency lifts the notion of consistency of deterministic constraints to infinite chance constraints. The essence of this novel notion of consistency is to be able to make an inference, in the presence of infinite scenarios in an uncertain environment, based on a restricted finite subset of scenarios with a certain confidence level and a threshold error. The confidence level is the probability that characterises the extent to which our inference, based on a subset of scenarios, is correct whereas the threshold error is the error range that we can tolerate while making such an inference. The statistical consistency acknowledges the fact that making a perfect inference in an uncertain environment and with an infinite number of scenarios is impossible. The statistical consistency, thus, with its reliance on a limited number of scenarios, a confidence level, and a threshold error constitutes a valid and an appropriate practical road that one can take in order to tackle infinite chance constraints. We design two novel approaches based on confidence intervals to enforce statistical consistency as well as a novel third approach based on hypothesis testing. We analyze the various methods theoretically as well as experimentally. Our empirical evaluation shows the weaknesses and strengths of each of the three methods in making a correct inference from a restricted subset of scenarios for enforcing statistical consistency. Overall, while the first two methods are able to make a correct inference in most of the cases, the third is a superior, effective, and robust one in all cases.
Databáze: OpenAIRE
Externí odkaz: