Author name cluster

Jean-Charles Régin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

IJCAI Conference 2025 Conference Paper

Large Language Model Meets Constraint Propagation

Alexandre Bonlarron
Florian Régin
Elisabetta De Maria
Jean-Charles Régin

Large Language Models (LLMs) excel at generating fluent text but struggle to enforce external constraints because they generate tokens sequentially without explicit control mechanisms. GenCP addresses this limitation by combining LLM predictions with Constraint Programming (CP) reasoning, formulating text generation as a Constraint Satisfaction Problem (CSP). In this paper, we improve GenCP by integrating Masked Language Models (MLMs) for domain generation, which allows bidirectional constraint propagation that leverages both past and future tokens. This integration bridges the gap between token-level prediction and structured constraint enforcement, leading to more reliable and constraint-aware text generation. Our evaluation on COLLIE benchmarks demonstrates that incorporating domain preview via MLM calls significantly improves GenCP's performance. Although this approach incurs additional MLM calls and, in some cases, increased backtracking, the overall effect is a more efficient use of LLM inferences and an enhanced ability to generate feasible and meaningful solutions, particularly in tasks with strict content constraints.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences

Alexandre Bonlarron
Jean-Charles Régin

Constrained text generation remains a challenging task, particularly when dealing with hard constraints. Traditional Natural Language Processing (NLP) approaches prioritize generating meaningful and coherent output. Also, the current state-of-the-art methods often lack the expressiveness and constraint satisfaction capabilities to handle such tasks effectively. This paper presents the Constraints First Framework to remedy this issue. This framework considers a constrained text generation problem as a discrete combinatorial optimization problem. It is solved by a constraint programming method that combines linguistic properties (e. g. , n-grams or language level) with other more classical constraints (e. g. , the number of characters, syllables, or words). Eventually, a curation phase allows for selecting the best-generated sentences according to perplexity using a large language model. The effectiveness of this approach is demonstrated by tackling a new more tediously constrained text generation problem: the iconic RADNER sentences problem. This problem aims to generate sentences respecting a set of quite strict rules defined by their use in vision and clinical research. Thanks to our CP-based approach, many new strongly constrained sentences have been successfully generated in an automatic manner. This highlights the potential of our approach to handle unreasonably constrained text generation scenarios.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Markov Constraint as Large Language Model Surrogate

Alexandre Bonlarron
Jean-Charles Régin

This paper presents NgramMarkov, a variant of the Markov constraints. It is dedicated to text generation in constraint programming (CP). It involves a set of n-grams (i. e. , sequence of n words) associated with probabilities given by a large language model (LLM). It limits the product of the probabilities of the n-gram of a sentence. The propagator of this constraint can be seen as an extension of the ElementaryMarkov constraint propagator, incorporating the LLM distribution instead of the maximum likelihood estimation of n-grams. It uses a gliding threshold, i. e. , it rejects n-grams whose local probabilities are too low, to guarantee balanced solutions. It can also be combined with a "look-ahead" approach to remove n-grams that are very unlikely to lead to acceptable sentences for a fixed-length horizon. This idea is based on the MDDMarkovProcess constraint propagator, but without explicitly using an MDD (Multi-Valued Decision Diagram). The experimental results show that the generated text is valued in a similar way to the LLM perplexity function. Using this new constraint dramatically reduces the number of candidate sentences produced, improves computation times, and allows larger corpora or smaller n-grams to be used. A real-world problem has been solved for the first time using 4-grams instead of 5-grams.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Constraints First: A New MDD-based Model to Generate Sentences Under Constraints

Alexandre Bonlarron
Aurélie Calabrèse
Pierre Kornprobst
Jean-Charles Régin

This paper introduces a new approach to generating strongly constrained texts. We consider standardized sentence generation for the typical application of vision screening. To solve this problem, we formalize it as a discrete combinatorial optimization problem and utilize multivalued decision diagrams (MDD), a well-known data structure to deal with constraints. In our context, one key strength of MDD is to compute an exhaustive set of solutions without performing any search. Once the sentences are obtained, we apply a language model (GPT-2) to keep the best ones. We detail this for English and also for French where the agreement and conjugation rules are known to be more complex. Finally, with the help of GPT-2, we get hundreds of bona-fide candidate sentences. When compared with the few dozen sentences usually available in the well-known vision screening test (MNREAD), this brings a major breakthrough in the field of standardized sentence generation. Also, as it can be easily adapted for other languages, it has the potential to make the MNREAD test even more valuable and usable. More generally, this paper highlights MDD as a convincing alternative for constrained text generation, especially when the constraints are hard to satisfy, but also for many other prospects.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Generalized Confidence Constraints

Guillaume Perez
Steve Malalel
Gael Glorian
Victor Jung
Alexandre Papadopoulos
Marie Pelleau
Wijnand Suijlen
Jean-Charles Régin

In robust optimization, finding a solution that solely respects the constraints is not enough. Usually, the uncertainty and unknown parameters of the model are represented by random variables. In such conditions, a good solution is a solution robust to most-likely assignments of these random variables. Recently, the Confidence constraint has been introduced by Mercier-Aubin et al. in order to enforce this type of robustness in constraint programming. Unfortunately, it is restricted to a conjunction of binary inequalities In this paper, we generalize the Confidence constraint to any constraint and propose an implementation based on Multi-valued Decision Diagrams (MDDs). The Confidence constraint is defined over a vector of random variables. For a given constraint C, and given a threshold, the Confidence constraint ensures that the probability for C to be satisfied by a sample of the random variables is greater than the threshold. We propose to use MDDs to represent the constraints on the random variables. MDDs are an efficient tool for representing combinatorial constraints, thanks to their exponential compression power. Here, both random and decision variables are stored in the MDD, and propagation rules are proposed for removing values of decision variables that cannot lead to robust solutions. Furthermore, for several constraints, we show that decision variables can be omitted from the MDD because lighter filtering algorithms are sufficient. This leads to gain an exponential factor in the MDD size. The experimental results obtained on a chemical deliveries problem in factories – where the chemicals consumption are uncertain – shows the efficiency of the proposed approach.

PDF Details DOI

AAAI Conference 2018 Conference Paper

Parallel Algorithms for Operations on Multi-Valued Decision Diagrams

Guillaume Perez
Jean-Charles Régin

Multi-valued Decision Diagrams (MDDs) have been extensively studied in the last ten years. Recently, efﬁcient algorithms implementing operators such as reduction, union, intersection, difference, etc. , have been designed. They directly deal with the graph structure of the MDD and a time reduction of several orders of magnitude in comparison to other existing algorithms have been observed. These operators have permitted a new look at MDDs, because extremely large MDDs can ﬁnally be manipulated as shown by the models used to solve complex application in music generation. However, MDDs become so large (50GB) that minutes are sometimes required to perform some operations. In order to accelerate the manipulation of MDDs, parallel algorithms are required. In this paper, we introduce such algorithms. We carefully design them in order to overcome inherent difﬁculties of the parallelization of sequential algorithms such as data dependencies, software lock-out, false sharing, or load balancing. As a result, we observe a speed-up, i. e. ratio between parallel and sequential runtimes, growing linearly with the number of cores.

PDF Details

JAIR Journal 2016 Journal Article

Embarrassingly Parallel Search in Constraint Programming

Arnaud Malapert
Jean-Charles Régin
Mohamed Rezgui

We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint subproblems which are then solved independently by workers. Our approach has three advantages: it is an efficient method; it involves almost no communication or synchronization between workers; and its implementation is made easy because the master and the workers rely on an underlying constraint solver, but does not require to modify it. This paper describes the method, and its applications to various constraint problems (satisfaction, enumeration, optimization). We show that our method can be adapted to different underlying solvers (Gecode, Choco2, OR-tools) on different computing infrastructures (multi-core, data centers, cloud computing). The experiments cover unsatisfiable, enumeration and optimization problems, but do not cover first solution search because it makes the results hard to analyze. The same variability can be observed for optimization problems, but at a lesser extent because the optimality proof is required. EPS offers good average performance, and matches or outperforms other available parallel implementations of Gecode as well as some solvers portfolios. Moreover, we perform an in-depth analysis of the various factors that make this approach efficient as well as the anomalies that can occur. Last, we show that the decomposition is a key component for efficiency and load balancing.

PDF Details DOI

ECAI Conference 2012 Conference Paper

An O(nlog n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization

Nicolas Beldiceanu
Mats Carlsson
Thierry Petit
Jean-Charles Régin

This paper gives an O( nlog  n) bound-consistency filtering algorithm for the conjunction alldifferent( V0, V1, &mldr; ,Vn− 1) &and; f( V0) &target; f( V1) &target; &mldr; &target; f( Vn− 1) ≤ cst, ( V0, V1, &mldr; ,Vn− 1, cst∈ +) , where (, &target;) is a commutative group, f is a unary function, and both &target; and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

Details

AIJ Journal 2005 Journal Article

An optimal coarse-grained arc consistency algorithm

Christian Bessière
Jean-Charles Régin
Roland H.C. Yap
Yuanlin Zhang

The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3. 1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3. 1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints.

Details DOI

AAAI Conference 1996 Conference Paper

Generalized Arc Consistency for Global Cardinality Constraint

Jean-Charles Régin

A global cardinality constraint (gee) is specified in terms of a set of variables X = { 21, .. ., zP} which take their values in a subset of V = { 01, .. ., vd}. It constrains the number of times a value V; 6 V is assigned to a variable in X to be in an interval [I; , ~1. Cardinality constraints have proved very useful in many real-life problems, such as scheduling, timetabling, or resource allocation. A gee is more general than a constraint of difference, which requires each interval to be [0, 11. In this p p a er, we present an efficient way of implementing generalized arc consistency for a gee. The algorithm we propose is based on a new theorem of flow theory. Its space complexity is 0(1X1 x IVl) and its time complexity is 0( 1x1” x IV/). We also show how this algorithm can efficiently be combined with other filtering techniques.

PDF Details

AAAI Conference 1994 Conference Paper

A Filtering Algorithm for Constraints of Difference in CSPs

Jean-Charles Régin

Many real-life Constraint Satisfaction Problems (CSPs) involve some constraints similar to the alldifferent constraints. These constraints are called constraints of difference. They are defined on a subset of variables by a set of tuples for which the values occuring in the same tuple are all different. In this paper, a new filtering algorithm for these constraints is presented. It achieves the generalized arc-consistency condition for these non-binary constraints. It is based on matching theory and its complexity is low. In fact, for a constraint defined on a subset of p variables having domains of cardinality at most d, its space complexity is OCpd) and its time complexity is O(p2d2). This filtering algorithm has been successfully used in the system RESYN (Vismara et al. 1992), to solve the subgraph isomorphism problem.

PDF Details