DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.15

Constraint Acquisition Based on Solution Counting

Authors: Christopher Coulombe and Claude-Guy Quimper

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract

We propose CABSC, a system that performs Constraint Acquisition Based on Solution Counting. In order to learn a Constraint Satisfaction Problem (CSP), the user provides positive examples and a Meta-CSP, i.e. a model of a combinatorial problem whose solution is a CSP. This Meta-CSP allows listing the potential constraints that can be part of the CSP the user wants to learn. It also allows stating the parameters of the constraints, such as the coefficients of a linear equation, and imposing constraints over these parameters. The CABSC reads the Meta-CSP using an augmented version of the language MiniZinc and returns the CSP that accepts the fewest solutions among the CSPs accepting all positive examples. This is done using a branch and bound where the bounding mechanism makes use of a model counter. Experiments show that CABSC is successful at learning constraints and their parameters from positive examples.

Cite as

Christopher Coulombe and Claude-Guy Quimper. Constraint Acquisition Based on Solution Counting. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coulombe_et_al:LIPIcs.CP.2022.15,
  author =	{Coulombe, Christopher and Quimper, Claude-Guy},
  title =	{{Constraint Acquisition Based on Solution Counting}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.15},
  URN =		{urn:nbn:de:0030-drops-166449},
  doi =		{10.4230/LIPIcs.CP.2022.15},
  annote =	{Keywords: Constraint acquisition, CSP, Model counting, Solution counting}
}

Search Results

Documents authored by Coulombe, Christopher

Constraint Acquisition Based on Solution Counting

Abstract

Cite as

Thanks for your feedback!

Could not send message