Abstract
Stochastic Constraint Programming introduces stochastic variables following a probability distribution to model uncertainty. In the classical setting, probability distributions are given and constant. We propose a framework in which random variables are given a set of possible distributions and only one should be selected. A solution is obtained when all variable distributions are assigned, and all decision variables are assigned too. In such a setting, a constraint on random variables limits the possible distributions its random variables may take. We generalize the notion of chance as the probability of satisfaction of a constraint, called probabilization, given variable distributions. Probabilization can be seen as a generalization of reification in a random setting whose result is a random variable. We define minimal arithmetic to work with stochastic variables having a variable distribution. Using the introduced representation, our framework can in theory save an exponential number of decisions, and represents problems that were previously not representable with finite integer domains. Finally, we model and solve two industrial problems that require this extension  virtual network configuration and assignment of chemical delivery  and show improvement in terms of quality of solution and speed.
BibTeX  Entry
@InProceedings{perez_et_al:LIPIcs.CP.2023.29,
author = {Perez, Guillaume and Glorian, Ga\"{e}l and Suijlen, Wijnand and Lallouet, Arnaud},
title = {{Distribution Optimization in Constraint Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {29:129:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959773003},
ISSN = {18688969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19066},
URN = {urn:nbn:de:0030drops190664},
doi = {10.4230/LIPIcs.CP.2023.29},
annote = {Keywords: Constraint Programming, Optimization, Stochastic Optimization}
}
Keywords: 

Constraint Programming, Optimization, Stochastic Optimization 
Collection: 

29th International Conference on Principles and Practice of Constraint Programming (CP 2023) 
Issue Date: 

2023 
Date of publication: 

22.09.2023 