Background: In Constraint Programming, constraint acquisition is the subfield that addresses the issue of modelling problems as sets of constraints, so that they can be solved by a constraint solver. This is a way to dramatically extend the use of Constraint Programming technology. Most active constraint acquisition systems suffer from two weaknesses. They require the explicit generation of the set of potential constraints (the bias), whose size can be prohibitive for practical use of these systems, and the answers to queries contain little information. Objectives: We introduce AcqNogoods, an active learning schema that does not require the construction of a bias. We then propose LlmAcq, an active learning system that incorporates a Large Language Model (LLM) component in the AcqNogoods schema. LlmAcq interprets the user’s answers given in natural language, leading to more informative communication. Methods: LlmAcq was instantiated with (i) a fine-tuned LLM encoder and (ii) a prompt-engineered LLM decoder. We evaluated both variants on classical logic-puzzle benchmarks (Purdey, Zebra, Sudoku, Kakuro). For greater realism, we also collected written feedback from 12 human subjects and used these data to design a pseudo-real experiment. Results: Across all benchmarks, LlmAcq dramatically decreases the number of queries, while learning constraints of arbitrary arity without the need of an explicit bias. The version of LlmAcq using a decoder LLM shows better accuracy and an interesting abstraction capability that allows it to learn several constraints from a single user’s answer. Conclusions: Our results suggest that combining natural-language feedback with bias-free learning is a promising step toward more user-friendly Constraint Programming modeling.

Active constraint acquisition aids users in specifying problem constraints by enabling queries that facilitate convergence on a unique target constraint network. Although various algorithms have been proposed to reduce the number of queries needed for convergence, few utilize the problem's structure. In this paper, we propose leveraging the problem's structure by transforming the partially learned constraint network into features vectors used as inputs for machine learning models. These models are trained to predict missing constraints, which are then proposed to the user via recommendation queries. Experimental results demonstrate significant performance improvements over existing approaches.

During the last decade several constraint acquisition systems have been proposed for assisting non-expert users in building constraint programming models. GENACQ is an algorithm based on generalization queries that can be plugged into many constraint acquisition systems. However, generalization queries require the aggregation of variables into types which is not always a simple task for non-expert users. In this paper, we propose a new algorithm that is able to learn types during the constraint acquisition process. The idea is to infer potential types by analyzing the structure of the current constraint network and to use the extracted types to ask generalization queries. Our approach gives good results although no knowledge on the types is provided.

Constraint acquisition assists a non-expert user in modeling her problem as a constraint network. In existing constraint acquisition systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a great number of such questions to learn all the constraints. In this paper, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ.

Asynchronous Backtracking is the standard search procedure for distributed constraint reasoning. It requires a total ordering on the agents. All polynomial space algorithms proposed so far to improve Asynchronous Backtracking by reordering agents during search only allow a limited amount of reordering. In this paper, we propose Agile-ABT, a search procedure that is able to change the ordering of agents more than previous approaches. This is done via the original notion of termination value, a vector of stamps labelling the new orders exchanged by agents during search. In Agile-ABT, agents can reorder themselves as much as they want as long as the termination value decreases as the search progresses. Our experiments show the good performance of Agile-ABT when compared to other dynamic reordering techniques.