Document Open Access Logo

Distribution Optimization in Constraint Programming

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

PDF
Thumbnail PDF

File

LIPIcs.CP.2023.29.pdf
  • Filesize: 0.85 MB
  • 19 pages

Document Identifiers

Author Details

Guillaume Perez
  • Huawei Technologies Ltd, CSI Paris, Boulogne-Billancourt, France
Gaël Glorian
  • Huawei Technologies Ltd, CSI Paris, Boulogne-Billancourt, France
Wijnand Suijlen
  • Huawei Technologies Ltd, CSI Paris, Boulogne-Billancourt, France
Arnaud Lallouet
  • Huawei Technologies Ltd, CSI Paris, Boulogne-Billancourt, France

Cite As Get BibTex

Guillaume Perez, Gaël Glorian, Wijnand Suijlen, and Arnaud Lallouet. Distribution Optimization in Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CP.2023.29

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Mathematics of computing → Solvers
  • Computing methodologies → Probabilistic reasoning
Keywords
  • Constraint Programming
  • Optimization
  • Stochastic Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Baum and Frank Wilczek. Supervised learning of probability distributions by neural networks. In Neural information processing systems, 1987. Google Scholar
  2. N Bharanidharan and Harikumar Rajaguru. Improved chicken swarm optimization to classify dementia mri images using a novel controlled randomness optimization algorithm. International Journal of Imaging Systems and Technology, 30(3):605-620, 2020. Google Scholar
  3. Giuseppe Calafiore and Marco C Campi. Uncertain convex programs: randomized solutions and confidence levels. Mathematical Programming, 102(1):25-46, 2005. Google Scholar
  4. Gilles Chabert et al. Ibex, an interval-based explorer, 2007. Google Scholar
  5. Gilles Chabert and Luc Jaulin. Contractor programming. Artificial Intelligence, 173(11):1079-1100, 2009. Google Scholar
  6. Abraham Charnes and William W Cooper. Chance-constrained programming. Management science, 6(1):73-79, 1959. Google Scholar
  7. Abraham Charnes and William W Cooper. Deterministic equivalents for optimizing and satisficing under chance constraints. Operations research, 11(1):18-39, 1963. Google Scholar
  8. Abraham Charnes, William Wager Cooper, and MJL Kirby. Chance-constrained programming: an extension of statistical method. In Optimizing methods in statistics, pages 391-402. Elsevier, 1971. Google Scholar
  9. Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A Servedio. Learning poisson binomial distributions. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 709-728, 2012. Google Scholar
  10. Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages 1183-1213. PMLR, 2014. Google Scholar
  11. Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck. Sequence variables for routing problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022), 2022. Google Scholar
  12. Mihai Dobrescu, Katerina Argyraki, and Sylvia Ratnasamy. Toward predictable performance in software Packet-Processing platforms. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), pages 141-154, 2012. Google Scholar
  13. Paul Emmerich, Daniel Raumer, Florian Wohlfart, and Georg Carle. Assessing soft-and hardware bottlenecks in pc-based packet forwarding systems. ICN 2015, 90, 2015. Google Scholar
  14. Hélène Fargier and Jérôme Lang. Uncertainty in constraint satisfaction problems: a probabilistic approach. In Symbolic and Quantitative Approaches to Reasoning and Uncertainty: European Conference ECSQARU'93 Granada, Spain, November 8-10, 1993 Proceedings 2, pages 97-104. Springer, 1993. Google Scholar
  15. Jakob Feldtkeller, David Knichel, Pascal Sasdrich, Amir Moradi, and Tim Güneysu. Randomness optimization for gadget compositions in higher-order masking. Cryptology ePrint Archive, 2022. Google Scholar
  16. Juliver Gil Herrera and Juan Felipe Botero. Resource allocation in nfv: A comprehensive survey. IEEE Transactions on Network and Service Management, 13(3):518-532, 2016. Google Scholar
  17. Brahim Hnich, Roberto Rossi, S Armagan Tarim, and Steven Prestwich. Synthesizing filtering algorithms for global chance-constraints. In Principles and Practice of Constraint Programming-CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 Proceedings 15, pages 439-453. Springer, 2009. Google Scholar
  18. Brahim Hnich, Roberto Rossi, S Armagan Tarim, and Steven Prestwich. Filtering algorithms for global chance constraints. Artificial Intelligence, 189:69-94, 2012. Google Scholar
  19. JN Hooker. Stochastic decision diagrams. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 138-154. Springer, 2022. Google Scholar
  20. Mark H Houck. A chance constrained optimization model for reservoir design and operation. Water Resources Research, 15(5):1011-1016, 1979. Google Scholar
  21. Bahareh Kargar, Mir Saman Pishvaee, Hamed Jahani, and Jiuh-Biing Sheu. Organ transportation and allocation problem under medical uncertainty: A real case study of liver transplantation. Transportation Research Part E: Logistics and Transportation Review, 134:101841, 2020. Google Scholar
  22. Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E Schapire, and Linda Sellie. On the learnability of discrete distributions. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 273-282, 1994. Google Scholar
  23. Lin Kemeng, Wang Xiaoyan, Xia Weijie, Zhang Jiaming, et al. Optimization of the randomness in einstein which based on monte carlo algorithms. In 2019 Chinese Control And Decision Conference (CCDC), pages 6305-6309. IEEE, 2019. Google Scholar
  24. Stefan Kern, Sibylle D Müller, Nikolaus Hansen, Dirk Büche, Jiri Ocenasek, and Petros Koumoutsakos. Learning probability distributions in continuous evolutionary algorithms-a comparative review. Natural Computing, 3:77-112, 2004. Google Scholar
  25. Minh Thanh Khong, Christophe Lecoutre, Pierre Schaus, and Yves Deville. Soft-regular with a prefix-size violation measure. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 333-343. Springer, 2018. Google Scholar
  26. Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009. Google Scholar
  27. Anna LD Latour, Behrouz Babaki, Daniël Fokkinga, Marie Anastacio, Holger H Hoos, and Siegfried Nijssen. Exact stochastic constraint optimisation with applications in network analysis. Artificial Intelligence, 304:103650, 2022. Google Scholar
  28. Pu Li, Harvey Arellano-Garcia, and Günter Wozny. Chance constrained programming approach to process optimization under uncertainty. Computers & chemical engineering, 32(1-2):25-45, 2008. Google Scholar
  29. Xiaoxia Lin, Stacy L Janak, and Christodoulos A Floudas. A new robust optimization approach for scheduling under uncertainty:: I. bounded uncertainty. Computers & chemical engineering, 28(6-7):1069-1085, 2004. Google Scholar
  30. Alexandre Mercier-Aubin, Ludwig Dumetz, Jonathan Gaudreault, and Claude-Guy Quimper. The confidence constraint: A step towards stochastic cp solvers. In International Conference on Principles and Practice of Constraint Programming, pages 759-773. Springer, 2020. Google Scholar
  31. Arkadi Nemirovski and Alexander Shapiro. Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17(4):969-996, 2007. Google Scholar
  32. François Pachet, Pierre Roy, Alexandre Papadopoulos, and Jason Sakellariou. Generating 1/f noise sequences as constraint satisfaction: The voss constraint. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. Google Scholar
  33. Bernardo K Pagnoncelli, Shabbir Ahmed, and Alexander Shapiro. Sample average approximation method for chance constrained programming: theory and applications. Journal of optimization theory and applications, 142(2):399-416, 2009. Google Scholar
  34. M Arenas Parra, A Bilbao Terol, B Pérez Gladish, and MV Rodrıguez Urıa. Solving a multiobjective possibilistic problem through compromise programming. European Journal of Operational Research, 164(3):748-759, 2005. Google Scholar
  35. Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988. Google Scholar
  36. Guillaume Perez, Steve Malalel, Gael Glorian, Victor Jung, Alexandre Papadopoulos, Marie Pelleau, Wijnand Suijlen, Jean-Charles Régin, and Arnaud Lallouet. Generalized confidence constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023. Google Scholar
  37. Guillaume Perez, Brendan Rappazzo, and Carla Gomes. Extending the capacity of 1/f noise generation. In International Conference on Principles and Practice of Constraint Programming, pages 601-610. Springer, 2018. Google Scholar
  38. Guillaume Perez and Jean-Charles Régin. MDDs are efficient modeling tools: An application to dispersion constraints. In Integration of AI and OR Techniques in Constraint Programming, 2017. Google Scholar
  39. Guillaume Perez and Jean-Charles Régin. Mdds: Sampling and probability constraints. In International Conference on Principles and Practice of Constraint Programming, pages 226-242. Springer, 2017. Google Scholar
  40. Gilles Pesant. Achieving domain consistency and counting solutions for dispersion constraints. INFORMS Journal on Computing, 27(4):690-703, 2015. URL: https://doi.org/10.1287/ijoc.2015.0654.
  41. Warren B Powell. A unified framework for stochastic optimization. European Journal of Operational Research, 275(3):795-821, 2019. Google Scholar
  42. Steven D Prestwich, Roberto Rossi, and S Armagan Tarim. Randomness as a constraint. In Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31-September 4, 2015, Proceedings 21, pages 351-366. Springer, 2015. Google Scholar
  43. Charles Prud’homme, Jean-Guillaume Fages, and Xavier Lorca. Choco solver documentation. TASC, INRIA Rennes, LINA CNRS UMR, 6241:13-42, 2016. Google Scholar
  44. Jean-Charles Régin. Arc consistency for global cardinality constraints with costs. In International Conference on Principles and Practice of Constraint Programming, pages 390-404. Springer, 1999. Google Scholar
  45. Francesca Rossi, Peter Van Beek, and Toby Walsh. Handbook of constraint programming. Elsevier, 2006. Google Scholar
  46. Roberto Rossi, Brahim Hnich, S Armagan Tarim, and Steven Prestwich. Confidence-based reasoning in stochastic constraint programming. Artificial Intelligence, 228:129-152, 2015. Google Scholar
  47. Christian Schulte and Guido Tack. View-based propagator derivation. Constraints, 18(1):75-107, 2013. Google Scholar
  48. Kalika Suksomboon, Nobutaka Matsumoto, Shuichi Okamoto, Michiaki Hayashi, and Yusheng Ji. Configuring a software router by the erlang-k-based packet latency prediction. IEEE Journal on Selected Areas in Communications, 36(3):422-437, 2018. Google Scholar
  49. S Armagan Tarim, Suresh Manandhar, and Toby Walsh. Stochastic constraint programming: A scenario-based approach. Constraints, 11:53-80, 2006. Google Scholar
  50. Joseph A Tatman and Ross D Shachter. Dynamic programming and influence diagrams. IEEE transactions on systems, man, and cybernetics, 20(2):365-379, 1990. Google Scholar
  51. Pascal Van Hentenryck and Laurent Michel. Domain views for constraint programming. In International Conference on Principles and Practice of Constraint Programming, pages 705-720. Springer, 2014. Google Scholar
  52. Willem-Jan Van Hoeve, Gilles Pesant, and Louis-Martin Rousseau. On global warming: Flow-based soft global constraints. Journal of Heuristics, 12(4):347-373, 2006. Google Scholar
  53. Toby Walsh. Stochastic constraint programming. In ECAI, volume 2, pages 111-115, 2002. Google Scholar
  54. Weijun Xie and Shabbir Ahmed. On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM Journal on Optimization, 28(2):1151-1182, 2018. Google Scholar
  55. Hui Zhang and Pu Li. Chance constrained programming for optimal power flow under uncertainty. IEEE Transactions on Power Systems, 26(4):2417-2424, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact