License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.29
URN: urn:nbn:de:0030-drops-190664
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19066/
Go to the corresponding LIPIcs Volume Portal

Perez, Guillaume ; Glorian, Gaël ; Suijlen, Wijnand ; Lallouet, Arnaud

Distribution Optimization in Constraint Programming

pdf-format:
LIPIcs-CP-2023-29.pdf (0.9 MB)

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:1--29:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19066},
  URN =		{urn:nbn:de:0030-drops-190664},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI