Talks and presentations

Generalizing Constraint Models in Constraint Acquisition

February 28, 2025

Poster, AAAI 2025, Philadelphia, USA

Constraint Acquisition (CA) aims to widen the use of constraint programming by assisting users in the modeling process. However, most CA methods suffer from a significant drawback: they learn a single set of individual constraints for a specific problem instance, but cannot generalize these constraints to the parameterized constraint specifications of the problem. In this paper, we addressed this limitation by proposing GenCon, a novel approach to learn parameterized constraint models capable of modeling varying instances of the same problem. To achieve this generalization, we make use of statistical learning techniques at the level of individual constraints. Specifically, we proposed to train a classifier to predict, for any possible constraint and parameterization, whether the constraint belongs to the problem.

A Tutorial on Constraint Acquisition

February 26, 2025

Tutorial, CPML 2025, Philadelphia, USA

Constraint Programming (CP) is a powerful paradigm for solving complex combinatorial problems, but its adoption is often hindered by the expertise required for modeling. Constraint Acquisition (CA) aims to mitigate this bottleneck by semi-automating the modeling process, exploiting machine learning methods. This tutorial provided an introduction to CA, covering both passive and interactive learning approaches, highlighting the recent integration of statistical Machine Learning methods that enhance robustness and efficiency. During the tutorial, state-of-the-art interactive CA methods implemented in the open source PyConA python library were demonstrated. Finally, we discussed current challenges and future directions in constraint acquisition research.

slides

A CPMpy-based Python Library for Constraint Acquisition - PyConA

February 26, 2025

Presentation, CPML 2025, Philadelphia, USA

Constraint Programming (CP) has been successfully used to model and solve complex combinatorial problems. However, modeling is often not trivial and requires expertise, which is a bottleneck to wider adoption. As a result, the field of Constraint Acquisition (CA) has evolved with the aim to (semi-) automate the modeling process by combining CP and Machine Learning. Passive CA acquires constraints using a set of pre-existing examples of solutions and non-solutions, while in (inter)active CA, the system is interacting with the user, e.g., asking whether a (partial) solution satisfies their (unspecified) constraints or not. Despite recent advancements in CA, a key limitation is the lack of a generic, easily accessible tool for practitioners and researchers to utilize these CA systems. In this work, we present PyConA, an open-source Python library for CA, which is based on the powerful CPMpy modeling library. PyConA currently includes only interactive CA methods, with the intention to also be extended to include passive CA systems. PyConA covers the state-of-the-art in interactive CA, including a variety of different algorithms, methods, and types of queries.

Demo

paper

repo

Constraint Modelling with LLMs Using In-Context Learning

February 26, 2025

Presentation, CPML 2025, Philadelphia, USA

Constraint Programming (CP) allows for the modelling and solving of a wide range of combinatorial problems. However, modelling such problems using constraints over decision variables still requires significant expertise, both in conceptual thinking and syntactic use of modelling languages. In this work, we explore the potential of using pre-trained Large Language Models (LLMs) as coding assistants, to transform textual problem descriptions into concrete and executable CP specifications. We present different transformation pipelines with explicit intermediate representations, and we investigate the potential benefit of various retrieval-augmented example selection strategies for in-context learning. We evaluate our approach on 2 datasets from the literature, namely NL4Opt (optimisation) and Logic Grid Puzzles (satisfaction), and a heterogeneous set of exercises from a CP course. The results show that pre-trained LLMs have promising potential for initialising the modelling process, with retrieval-augmented in-context learning significantly enhancing their modelling capabilities.

slides

CP24 Tutorial: Constraint Acquisition - A tutorial on Learning Constraint Models

September 05, 2024

Tutorial, CP 2024, Girona, Spain

Constraint Programming (CP) is a powerful paradigm for solving complex combinatorial problems, but its adoption is often hindered by the expertise required for modeling. Constraint Acquisition (CA) aims to mitigate this bottleneck by semi-automating the modeling process. This tutorial provides a comprehensive introduction to CA, covering both passive and interactive learning approaches.

Generalizing Constraint models in Constraint Acquisition

September 02, 2024

Presentation on Workshop, CP-PTHG 2024, Girona, Spain

Our workshop paper on “Generalizing Constraint models in Constraint Acquisition” was presented in the Progress Towards the Holy Grail workshop at the CP Conference.

Abstract: Constraint Acquisition (CA) aims to widen the use of constraint programming by helping users in the modeling process. However, most CA methods learn one ground CSP: a set of individual constraints for a specific problem instance. We focus on generalizing ground CSPs, by learning parameterized constraint models that can model multiple instances of the same problem.

Learning to Learn and to Generalize in Interactive Constraint Acquisition

April 05, 2024

Invited Talk, Department of Electrical and Computer Engineering, Ioannina, Greece

Constraint Programming (CP) has been successfully used to model and solve complex combinatorial problems. However, modelling is often not trivial and requires expertise, which is a bottleneck to the wider adoption of CP technology. In Constraint Acquisition (CA), the goal is to assist the user by automatically learning the model. In (inter)active CA, this is done by interactively posting queries to the user, e.g., asking whether a (partial) example satisfies their (unspecified) constraints or not. While interactive CA methods learn the constraints of a given problem, the learning is related to symbolic concept learning, as the goal is to learn an exact representation. However, a large number of queries is required by most systems to learn the model, which is a major limitation. In this talk, I discussed how we alleviated this limitation by tightening the connection of CA and Machine Learning (ML), by, for the first time in interactive CA, exploiting statistical ML methods to guide interactive CA queries.

Learning to Learn in Interactive Constraint Acquisition

February 22, 2024

Poster, AAAI 2024, Vancouver, Canada

Our paper on “Learning to Learn in Interactive Constraint Acquisition” was presented in AAAI24. In Constraint Acquisition (CA), the goal is to assist the user by automatically learning the model. In (inter)active CA, this is done by interactively posting queries to the user, e.g., asking whether a partial solution satisfies their (unspecified) constraints or not. In our proposed approach, the system actually learns (implicitely) the structure of the problem, using classifiers to learn the existing patterns, using a feature representation of the constraints. The query-based learning is making this explicit, confirming it through queries to the user. This resulted in up to 70% reduction in the number of queries needed to learn the correct set of constraints!

Invited talk: Chatbots and LLMs for Constraint Programming: Opportunities and Challenges - With Serdar Kadioğlu

February 21, 2024

Talk, AAAI 2024 - CPML Bridge, Vancouver, Canada

Twenty-seven years ago, E. Freuder highlighted that “Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it”. Nowadays, CP users have great modeling tools available (like Minizinc and CPMpy), allowing them to formulate the problem and then let a solver do the rest of the job, getting closer to the stated goal. However, this still requires the CP user to know the formalism and respect it. Another significant challenge lies in the expertise required to effectively model combinatorial problems. All this limits the wider adoption of CP. In this discussion, we investigated how to leverage NLP approaches to model constraint problems from textual description. We discussed bottom-up and top-down approaches, by either building each required component (e.g., variables, constraints, objective, etc.) and then combining them together, or using pre-trained Large Language Models to directly extract the models. We presented early results with both.

Explainable Constraint Solving - A Hands-On Tutorial (video)

August 29, 2023

Tutorial, CP 2023, Toronto, Canada

Explainable constraint solving is a sub-field of explainable AI (XAI) concerned with explaining constraint (optimization) problems. Although constraint models are explicit: they are written down in terms of individual constraints that need to be satisfied, the solution to such models can be non-trivial to understand. Driven by the use-case of nurse scheduling, we will demonstrate the type of questions a user can have about (non)-solutions, as well as reviewing what kind of computational tools are available today to answer such questions. We will cover classical methods such as MUS/MCS extraction, and more recent advances in the field such as step-wise explanations, constraint relaxation methods and counterfactual solutions. We will demonstrate and give special attention to techniques that we have successfully (re)implemented on top of the CPMpy constraint solving library, and hence can be readily used today.

Guided Bottom-up Interactive Constraint Acquisition

August 29, 2023

Presentation, CP 2023, Toronto, Canada

Constraint Acquisition (CA) systems can be used to assist in the modeling of constraint satisfaction problems. In (inter)active CA, the system is given a set of candidate constraints and posts queries to the user with the goal of finding the right constraints among the candidates. Current interactive CA algorithms suffer from at least two major bottlenecks. First, in order to converge, they require a large number of queries to be asked to the user. Second, they cannot handle large sets of candidate constraints, since these lead to large waiting times for the user. For this reason, the user must have fairly precise knowledge about what constraints the system should consider. In this presentation, I discuss how we alleviated these bottlenecks in our CP2023 paper, presenting our two novel methods that improve the efficiency of CA.

Holy Grail 2.0: From Natural Language to Constraint Models

August 27, 2023

Presentation, CP 2023 - PTHG Workshop, Toronto, Canada

Twenty-seven years ago, E. Freuder highlighted that “Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it”. Nowadays, CP users have great modeling tools available (like Minizinc and CPMpy), allowing them to formulate the problem and then let a solver do the rest of the job, getting closer to the stated goal. However, this still requires the CP user to know the formalism and respect it. Another significant challenge lies in the expertise required to effectively model combinatorial problems. All this limits the wider adoption of CP. In this position paper, we investigate a possible approach to leverage pre-trained Large Language Models to extract models from textual problem descriptions. More specifically, we take inspiration from the Natural Language Processing for Optimization (NL4OPT) challenge and present early results with a decomposition-based prompting approach to GPT Models.

ACP Summer School 2023: Constraint Acquisition - Learning Constraint Models from Data (video)

July 14, 2023

Talk, ACP Summer School, Leuven, Belgium

The basic assumption in CP is that the user models the problem, and a solver is then used to solve it. However, expressing a combinatorial problem as a constraint model is not always straightforward. As a result, modelling is considered to be a bottleneck for the wider use of CP. To overcome this obstacle, several techniques have been proposed for modeling a constraint problem (semi-)automatically. In constraint acquisition, the model of a constraint problem is acquired (i.e., learned) using a set of examples of solutions, and possibly non-solutions. The talk is an overview of constraint acquisition research, in which learning techniques are used to learn constraint models from data. This is done either in a passive setting, using an existing set of solutions and/or non-solutions of the problem, or in an active setting where the system interacts with the user to model the problem. I discuss both passive and (inter)active learning, the current state-of-the-art and the connections to the machine learning field. Finally, I focus on the current challenges in Constraint Acquisition.

Learning constraint models from data

February 07, 2023

Talk, AAAI 2023 - CPML Bridge, Washington, D.C., US

Constraint programming (CP) is widely used for solving real-world problems. The basic assumption in CP is that the user models the problem and a solver is then used to solve it. Despite the many successful applications of CP on combinatorial problems from various domains, there are still challenges to be faced in order to make CP technology even more widely used. A major bottleneck in the use of CP is modeling. Expressing a combinatorial problem as a set of constraints over decision variables requires substantial expertise, and this non-trivial task is often a major bottleneck for the widespread adoption of CP.