1 Search Results for "Vavrille, Mathieu"

Document
DOI: 10.4230/LIPIcs.CP.2021.56
Solution Sampling with Random Table Constraints

Authors: Mathieu Vavrille, Charlotte Truchet, and Charles Prud'homme

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Constraint programming provides generic techniques to efficiently solve combinatorial problems. In this paper, we tackle the natural question of using constraint solvers to sample combinatorial problems in a generic way. We propose an algorithm, inspired from Meel’s ApproxMC algorithm on SAT, to add hashing constraints to a CP model in order to split the search space into small cells of solutions. By sampling the solutions in the restricted search space, we can randomly generate solutions without revamping the model of the problem. We ensure the randomness by introducing a new family of hashing constraints: randomly generated tables. We implemented this solving method using the constraint solver Choco-solver. The quality of the randomness and the running time of our approach are experimentally compared to a random branching strategy. We show that our approach improves the randomness while being in the same order of magnitude in terms of running time.
Cite as

Mathieu Vavrille, Charlotte Truchet, and Charles Prud'homme. Solution Sampling with Random Table Constraints. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vavrille_et_al:LIPIcs.CP.2021.56,
  author =	{Vavrille, Mathieu and Truchet, Charlotte and Prud'homme, Charles},
  title =	{{Solution Sampling with Random Table Constraints}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.56},
  URN =		{urn:nbn:de:0030-drops-153477},
  doi =		{10.4230/LIPIcs.CP.2021.56},
  annote =	{Keywords: solutions, sampling, table constraint}
}
  • Refine by Author
  • 1 Prud'homme, Charles
  • 1 Truchet, Charlotte
  • 1 Vavrille, Mathieu

  • Refine by Classification
  • 1 Computing methodologies → Randomized search

  • Refine by Keyword
  • 1 sampling
  • 1 solutions
  • 1 table constraint

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact