2 Search Results for "Vavrille, Mathieu"

Document

DOI: 10.4230/LIPIcs.CP.2025.40

An Efficient and Uniform CSP Solution Generator Generator

Authors: Ghiles Ziat and Martin Pépin

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract

Constraint-based random testing is a powerful technique which aims at generating random test cases to verify functional properties of a program. Its objective is to determine whether a function satisfies a given property for every possible input. This approach requires firstly defining the property to satisfy, then secondly to provide a "generator of inputs" able to feed the program with the inputs generated. Besides, function inputs often need to satisfy certain constraints to ensure the function operates correctly, which makes the crafting of such a generator a hard task. In this paper, we are interested in the problem of manufacturing a uniform and efficient generator for the solutions of a CSP. In order to do that, we propose a specialized solving method that produces a well-suited representation for random sampling. Our solving method employs a dedicated propagation scheme based on the hypergraph representation of a CSP, and a custom split heuristic called birdge-first that emphasizes the interests of our propagation scheme. The generators we build are general enough to handle a wide range of use-cases. They are moreover uniform by construction, iterative and self-improving. We present a prototype built upon the AbSolute constraint solving library and demonstrate its performances on several realistic examples.

Cite as

Ghiles Ziat and Martin Pépin. An Efficient and Uniform CSP Solution Generator Generator. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ziat_et_al:LIPIcs.CP.2025.40,
  author =	{Ziat, Ghiles and P\'{e}pin, Martin},
  title =	{{An Efficient and Uniform CSP Solution Generator Generator}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.40},
  URN =		{urn:nbn:de:0030-drops-239010},
  doi =		{10.4230/LIPIcs.CP.2025.40},
  annote =	{Keywords: Constraint Programming, Property-based Testing}
}

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.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 Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2021

Refine by Author
1 Prud'homme, Charles
1 Pépin, Martin
1 Truchet, Charlotte
1 Vavrille, Mathieu
1 Ziat, Ghiles

Refine by Series/Journal
2 LIPIcs

Refine by Classification
2 Computing methodologies → Randomized search

Refine by Keyword
1 Constraint Programming
1 Property-based Testing
1 sampling
1 solutions
1 table constraint

2 Search Results for "Vavrille, Mathieu"

An Efficient and Uniform CSP Solution Generator Generator

Abstract

Cite as

Solution Sampling with Random Table Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message