Christophe Lecoutre

AAAI Conference 2026 Conference Paper

Aperiodic Tiling and Rhythmic Canons: A CP Journey

• Guillaume Derval
• Christophe Lecoutre

The Aperiodic Tiling Complements Problem (ATCP) involves finding the full set of (normalized) aperiodic complements of a given pattern. This has become a classic problem in music theory, with some recent attempts to model it using Integer Linear Programming (ILP) and Boolean Satisfiability (SAT) frameworks. In this paper, we develop and compare different models of ATCP encoded with Constraint Programming (CP). The most effective approach admits two phases: a first one that allows us to merge (join) several subsets of linear constraints under the form of tables with large arity, and a second one that advantageously exploits the generated tables to discard periodic tiling complements. Our experimental results show that our approach significantly outperforms the state-of-the-art, solving every instance of a classical benchmark (standard Vuza rhythms for canons with periods set up to 900) in a time between 5 seconds and 2 minutes (except the largest instance being solved in 18 minutes).

IJCAI Conference 2022 Conference Paper

Best Heuristic Identification for Constraint Satisfaction

• Frederic Koriche
• Christophe Lecoutre
• Anastasia Paparrizou
• Hugues Wattez

In constraint satisfaction problems, the variable ordering heuristic takes a central place by selecting the variables to branch on during backtrack search. As many hand-crafted branching heuristics have been proposed in the literature, a key issue is to identify, from a pool of candidate heuristics, which one is the best for solving a given constraint satisfaction task. Based on the observation that modern constraint solvers are using restart sequences, the best heuristic identification problem can be cast in the context of multi-armed bandits as a non-stochastic best arm identification problem. Namely, during each run of some given restart sequence, the bandit algorithm selects a branching heuristic and receives a reward for this heuristic before proceeding to the next run. The goal is to identify the best heuristic using few runs, and without any stochastic assumption about the constraint solver. In this study, we propose an adaptive variant of Successive Halving that exploits Luby's universal restart sequence. We analyze the convergence of this bandit algorithm in the non-stochastic setting, and we demonstrate its empirical effectiveness on various constraint satisfaction benchmarks.

ECAI Conference 2020 Conference Paper

Learning Variable Ordering Heuristics with Multi-Armed Bandits and Restarts

• Hugues Wattez
• Frédéric Koriche
• Christophe Lecoutre
• Anastasia Paparrizou
• Sébastien Tabary

In constraint-based applications, the user is often required to be an expert as, for a given problem instance, many parameters of the used solver must be manually tuned to improve its efficiency. Clearly, this background knowledge burdens the spread of constraint programming technology to non-expert users. In order to alleviate this issue, the idea of “autonomous” constraint solving is to adjust the solver parameters and to efficiently handle any problem instance without manual tuning. Notably, the choice of the variable ordering heuristic can lead to drastically different performances. A key question arises then: how can we find the best variable ordering heuristic for a problem instance, given a set of available heuristics provided by the solver? To answer this question, we propose an algorithmic framework that combines multi-armed bandits and restarts. Each candidate heuristic is viewed as an arm, and the framework learns to estimate the best heuristic using a multi-armed bandit algorithm. The common mechanism of restarts is used to provide feedback for reinforcing the bandit algorithm. Based on a thorough experimental evaluation, we demonstrate that this framework is able to find the best heuristic for most problem instances; notably, it outperforms the state-of-the-art in terms of time and solved instances.

LPAR Conference 2020 Conference Paper

NACRE - A Nogood And Clause Reasoning Engine

• Gael Glorian
• Jean-Marie Lagniez
• Christophe Lecoutre

NACRE, for Nogood And Clause Reasoning Engine, is a constraint solver written in C++. It is based on a modular architecture designed to work with generic constraints while implementing several state-of-the-art search methods and heuristics. Interestingly, its data structures have been carefully designed to play around nogoods and clauses, making it suit- able for implementing learning strategies. NACRE was submitted to the CSP MiniTrack of the 2018 and 2019 XCSP3 [8] competitions where it took the first place. This paper gives a general description of NACRE as a framework. We present its kernel, the available search algorithms, and the default settings (notably, used for XCSP3 competitions), which makes NACRE efficient in practice when used as a black-box solver.

ECAI Conference 2020 Conference Paper

Segmented Tables: An Efficient Modeling Tool for Constraint Reasoning

• Gilles Audemard
• Christophe Lecoutre
• Mehdi Maamar

These last years, there has been a growing interest for structures like tables and decision diagrams in Constraint Programming (CP). This is due to the universal character of these structures, enabling the representation of any (group of) constraints under extensional form, and to the efficient filtering algorithms developed for constraints based on (ordinary/short/compressed/smart) tables and multi-valued decision diagrams. In this paper, we propose the concept of segmented tables where entries can combine ordinary values, universal values (*) and sub-tables. Segmented tables can be seen as a generalization of compressed tables. We propose an algorithm enforcing Generalized Arc Consistency (GAC) on segmented table constraints, and show their modeling and practical interests on a realistic problem.

IJCAI Conference 2018 Conference Paper

Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets

• Hélène Verhaeghe
• Christophe Lecoutre
• Pierre Schaus

Multi-Valued Decision Diagrams (MDDs) are instrumental in modeling combinatorial problems with Constraint Programming. In this paper, we propose a related data structure called sMDD (semi-MDD) where the central layer of the diagrams is non-deterministic. We show that it is easy and efficient to transform any table (set of tuples) into an sMDD. We also introduce a new filtering algorithm, called Compact-MDD, which is based on bitwise operations, and can be applied to both MDDs and sMDDs. Our experimental results show the practical interest of our approach, both in terms of compression and filtering speed.

IJCAI Conference 2017 Conference Paper

Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints

• Baudouin Le Charlier
• Minh Thanh Khong
• Christophe Lecoutre
• Yves Deville

The smart table constraint represents a powerful modeling tool that has been recently introduced. This constraint allows the user to represent compactly a number of well-known (global) constraints and more generally any arbitrarily structured constraints, especially when disjunction is at stake. In many problems, some constraints are given under the basic and simple form of tables explicitly listing the allowed combinations of values. In this paper, we propose an algorithm to convert automatically any (ordinary) table into a compact smart table. Its theoretical time complexity is shown to be quadratic in the size of the input table. Experimental results demonstrate its compression efficiency on many constraint cases while showing its reasonable execution time. It is then shown that using filtering algorithms on the resulting smart table is more efficient than using state of the art filtering algorithms on the initial table.

AAAI Conference 2017 Conference Paper

Extending Compact-Table to Negative and Short Tables

• HŽlne Verhaeghe
• Christophe Lecoutre
• Pierre Schaus

Table constraints are very useful for modeling combinatorial constrained problems, and thus play an important role in Constraint Programming (CP). During the last decade, many algorithms have been proposed for enforcing the property known as Generalized Arc Consistency (GAC) on such constraints. A state-of-the art GAC algorithm called Compact- Table (CT), which has been recently proposed, significantly outperforms all previously proposed algorithms. In this paper, we extend this algorithm in order to deal with both short supports and negative tables, i. e. , tables that contain universal values and conflicts. Our experimental results show the interest of using this fast general algorithm.

AIJ Journal 2016 Journal Article

Computing and restoring global inverse consistency in interactive constraint satisfaction

• Christian Bessiere
• Hélène Fargier
• Christophe Lecoutre

Some applications require the interactive resolution of a constraint problem by a human user. In such cases, it is highly desirable that the person who interactively solves the problem is not given the choice to select values that do not lead to solutions. We call this property global inverse consistency. Existing systems simulate this either by maintaining arc consistency after each assignment performed by the user or by compiling offline the problem as a multi-valued decision diagram. In this article, we define several questions related to global inverse consistency and analyze their complexity. Despite their theoretical intractability, we propose several algorithms for enforcing and restoring global inverse consistency and we show that the best version is efficient enough to be used in an interactive setting on several configuration and design problems.

AIJ Journal 2015 Journal Article

STR3: A path-optimal filtering algorithm for table constraints

• Christophe Lecoutre
• Chavalit Likitvivatanavong
• Roland H.C. Yap

Constraint propagation is a key to the success of Constraint Programming (CP). The principle is that filtering algorithms associated with constraints are executed in sequence until quiescence is reached. Many such algorithms have been proposed over the years to enforce the property called Generalized Arc Consistency (GAC) on many types of constraints, including table constraints that are defined extensionally. Recent advances in GAC algorithms for extensional constraints rely on directly manipulating tables during search. This is the case with a simple approach called Simple Tabular Reduction (STR), which systematically maintains tables of constraints to their relevant lists of tuples. In particular, STR2, a refined STR variant is among the most efficient GAC algorithms for positive table constraints. In this paper, we revisit this approach by proposing a new GAC algorithm called STR3 that is specifically designed to enforce GAC during backtrack search. By indexing tables and reasoning from deleted values, we show that STR3 can avoid systematically iterating over the full set of current tuples, contrary to STR2. An important property of STR3 is that it can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. We also study a variant of STR3, based on an optimal circular way for traversing tables, and discuss the relationship of STR3 with two other optimal GAC algorithms introduced in the literature, namely, GAC4 and AC5TC-Tr. Finally, we demonstrate experimentally how STR3 is competitive with the state-of-the-art. In particular, our extensive experiments show that STR3 is generally faster than STR2 when the average size of tables is not reduced too drastically during search, making STR3 complementary to STR2.

AAAI Conference 2013 Conference Paper

Extending STR to a Higher-Order Consistency

• Christophe Lecoutre
• Anastasia Paparrizou
• Kostas Stergiou

One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerous specialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC), have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper, we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max restricted pairwise consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.

ECAI Conference 2012 Conference Paper

A Path-Optimal GAC Algorithm for Table Constraints

• Christophe Lecoutre
• Chavalit Likitvivatanavong
• Roland H. C. Yap

Filtering by Generalized Arc Consistency (GAC) is a fundamental technique in Constraint Programming. Recent advances in GAC algorithms for extensional constraints rely on direct manipulation of tables during search. Simple Tabular Reduction (STR), which systematically removes invalid tuples from tables, has been shown to be a simple yet efficient approach. STR2, a refinement of STR, is considered to be among the best filtering algorithms for positive table constraints. In this paper, we introduce a new GAC algorithm called STR3 that is specifically designed to enforce GAC during search. STR3 can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. Our experiments show that STR3 is much faster than STR2 when the average size of the tables is not reduced drastically during search.

KR Conference 2010 Conference Paper

A Class of df-consistencies for Qualitative Constraint Networks

• Jean-François Condotta
• Christophe Lecoutre

In this paper, we introduce a new class of local consistencies, called f -consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition () and a mapping f that provides a covering for each relation of the considered qualitative calculus. We study the connections existing between some properties of the introduced mappings and the relative inference strength of f -consistencies. The consistency obtained by the usual closure under weak composition corresponds to the weakest element of the class, whereas f -consistencies stronger than weak composition open new promising perspectives. Interestingly, the class of f -consistencies is shown to form a complete lattice where the partial order denotes the relative strength of every two consistencies. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any “well-behaved” consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.

AIJ Journal 2009 Journal Article

Reasoning from last conflict(s) in constraint programming

• Christophe Lecoutre
• Lakhdar Saïs
• Sébastien Tabary
• Vincent Vidal

Constraint programming is a popular paradigm to deal with combinatorial problems in artificial intelligence. Backtracking algorithms, applied to constraint networks, are commonly used but suffer from thrashing, i. e. the fact of repeatedly exploring similar subtrees during search. An extensive literature has been devoted to prevent thrashing, often classified into look-ahead (constraint propagation and search heuristics) and look-back (intelligent backtracking and learning) approaches. In this paper, we present an original look-ahead approach that allows to guide backtrack search toward sources of conflicts and, as a side effect, to obtain a behavior similar to a backjumping technique. The principle is the following: after each conflict, the last assigned variable is selected in priority, so long as the constraint network cannot be made consistent. This allows us to find, following the current partial instantiation from the leaf to the root of the search tree, the culprit decision that prevents the last variable from being assigned. This way of reasoning can easily be grafted to many variations of backtracking algorithms and represents an original mechanism to reduce thrashing. Moreover, we show that this approach can be generalized so as to collect a (small) set of incompatible variables that are together responsible for the last conflict. Experiments over a wide range of benchmarks demonstrate the effectiveness of this approach in both constraint satisfaction and automated artificial intelligence planning.

ECAI Conference 2008 Conference Paper

A Decomposition Technique for Max-CSP

• Hachemi Bennaceur
• Christophe Lecoutre
• Olivier Roussel

The objective of the Maximal Constraint Satisfaction Problem (Max-CSP) is to find an instantiation which minimizes the number of constraint violations in a constraint network. In this paper, inspired from the concept of inferred disjunctive constraints introduced by Freuder and Hubbe, we show that it is possible to exploit the arc-inconsistency counts, associated with each value of a network, in order to avoid exploring useless portions of the search space. The principle is to reason from the distance between the two best values in the domain of a variable, according to such counts. From this reasoning, we can build a decomposition technique which can be used throughout search in order to decompose the current problem into easier sub-problems. Interestingly, this approach does not depend on the structure of the constraint graph, as it is usually proposed. Alternatively, we can dynamically post hard constraints that can be used locally to prune the search space. The practical interest of our approach is illustrated, using this alternative, with an experimentation based on a classical branch and bound algorithm, namely PFC-MRDAC.

IJCAI Conference 2007 Conference Paper

• Christophe Lecoutre
• Lakhdar Sais
• S
• eacute; bastien Tabary
• Vincent Vidal

In this paper, nogood recording is investigated within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i. e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of our approach.

IJCAI Conference 2007 Conference Paper

• Christophe Lecoutre
• Fred Hemery

In an Arc Consistency (AC) algorithm, a residual support, or residue, is a support that has been stored during a previous execution of the procedure which determines if a value is supported by a constraint. The point is that a residue is not guaranteed to represent a lower bound of the smallest current support of a value. In this paper, we study the theoretical impact of exploiting residues with respect to the basic algorithm AC3. First, we prove that AC3rm (AC3 with multi-directional residues) is optimal for low and high constraint tightness. Second, we show that when AC has to be maintained during a backtracking search, MAC2001 presents, with respect to MAC3rm, an overhead in O(med) per branch of the binary tree built by MAC, where m denotes the number of refutations of the branch, e the number of constraints and d the greatest domain size of the constraint network. One consequence is that MAC3rm admits a better worst-case time complexity than MAC2001 for a branch involving m refutations when either m > d^2 or m > d and the tightness of any constraint is either low or high. Our experimental results clearly show that exploiting residues allows enhancing MAC and SAC algorithms.

AAAI Conference 2007 Conference Paper

Conservative Dual Consistency

• Christophe Lecoutre

Consistencies are properties of Constraint Networks (CNs) that can be exploited in order to make inferences. When a significant amount of such inferences can be performed, CNs are much easier to solve. In this paper, we interest ourselves in relation filtering consistencies for binary constraints, i. e. consistencies that allow to identify inconsistent pairs of values. We propose a new consistency called Dual Consistency (DC) and relate it to Path Consistency (PC). We show that Conservative DC (CDC, i. e. DC with only relations associated with the constraints of the network considered) is more powerful, in terms of filtering, than Conservative PC (CPC). Following the approach of Mac Gregor, we introduce an algorithm to establish (strong) CDC with a very low worst-case space complexity. Even if the relative efficiency of the algorithm introduced to establish (strong) CDC partly depends on the density of the constraint graph, the experiments we have conducted show that, on many series of CSP instances, CDC is largely faster than CPC (up to more than one order of magnitude). Besides, we have observed that enforcing CDC in a preprocessing stage can significantly speed up the resolution of hard structured instances.

AIJ Journal 2007 Journal Article

Random constraint satisfaction: Easy generation of hard (satisfiable) instances

• Ke Xu
• Frédéric Boussemart
• Fred Hemery
• Christophe Lecoutre

In this paper, we show that the models of random CSP instances proposed by Xu and Li [K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12 (2000) 93–103; K. Xu, W. Li, Many hard examples in exact phase transitions with application to generating hard satisfiable instances, Technical report, CoRR Report cs. CC/0302001, Revised version in Theoretical Computer Science 355 (2006) 291–302] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i. e. , to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.

AAAI Conference 2007 Conference Paper

Transposition Tables for Constraint Satisfaction

• Christophe Lecoutre
• Sebastien Tabary

In this paper, a state-based approach for the Constraint Satisfaction Problem (CSP) is proposed. The key novelty is an original use of state memorization during search to prevent the exploration of similar subnetworks. Classical techniques to avoid the resurgence of previously encountered conflicts involve recording conflict sets. This contrasts with our statebased approach which records subnetworks – a snapshot of some selected domains – already explored. This knowledge is later used to either prune inconsistent states or avoid recomputing the solutions of these subnetworks. Interestingly enough, the two approaches present some complementarity: different states can be pruned from the same partial instantiation or conflict set, whereas different partial instantiations can lead to the same state that needs to be explored only once. Also, our proposed approach is able to dynamically break some kinds of symmetries (e. g. neighborhood interchangeability). The obtained experimental results demonstrate the promising prospects of state-based search.

ECAI Conference 2006 Conference Paper

Extracting MUCs from Constraint Networks

• Fred Hemery
• Christophe Lecoutre
• Lakhdar Saïs
• Frédéric Boussemart

We address the problem of extracting Minimal Unsatisfiable Cores (MUCs) from constraint networks. This computationally hard problem has a practical interest in many application domains such as configuration, planning, diagnosis, etc. Indeed, identifying one or several disjoint MUCs can help circumscribe different sources of inconsistency in order to repair a system. In this paper, we propose an original approach that involves performing successive runs of a complete backtracking search, using constraint weighting, in order to surround an inconsistent part of a network, before identifying all transition constraints belonging to a MUC using a dichotomic process. We show the effectiveness of this approach, both theoretically and experimentally.

ECAI Conference 2006 Conference Paper

Last Conflict Based Reasoning

• Christophe Lecoutre
• Lakhdar Saïs
• Sébastien Tabary
• Vincent Vidal 0001

In this paper, we propose an approach to guide search to sources of conflicts. The principle is the following: the last variable involved in the last conflict is selected in priority, as long as the constraint network can not be made consistent, in order to find the (most recent) culprit variable, following the current partial instantiation from the leaf to the root of the search tree. In other words, the variable ordering heuristic is violated, until a backtrack to the culprit variable occurs and a singleton consistent value is found. Consequently, this way of reasoning can easily be grafted to many search algorithms and represents an original way to avoid thrashing. Experiments over a wide range of benchmarks demonstrate the effectiveness of this approach.

IJCAI Conference 2005 Conference Paper

A Greedy Approach to Establish Singleton Arc Consistency

• Christophe Lecoutre
• Stéphane

In this paper, we propose a new approach to establish Singleton Arc Consistency (SAC) on constraint networks. While the principle of existing SAC algorithms involves performing a breadth-first search up to a depth equal to 1, the principle of the two algorithms introduced in this paper involves performing several runs of a greedy search (where at each step, arc consistency is maintained). It is then an original illustration of applying inference (i. e. establishing singleton arc consistency) by search. Using a greedy search allows benefiting from the incrementality of arc consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. Furthermore, both space and time complexities are quite competitive.

ECAI Conference 2004 Conference Paper

Boosting Systematic Search by Weighting Constraints

• Frédéric Boussemart
• Fred Hemery
• Christophe Lecoutre
• Lakhdar Saïs

LOPSTR Conference 1992 Conference Paper

Abstract Interpretation and Recursive Behaviour of Logic Programs

• Christophe Lecoutre
• Philippe Devienne
• Patrick Lebègue

Abstract We propose a general abstract interpretation based on the recursive behaviour study of Prolog programs. This abstract interpretation allows both the dataflow analysis of a program execution and the automatic derivation of some program properties. First, we introduce a new notion: the limited-unfolding loop (abbreviated to lul). Roughly speaking, a tree t satisfies a lul m iff the leaf of the branch corresponding to the unfolding of the loop m is labelled with a constant. Instead of a term-groundedness analysis, our study can be seen as a “branch-groundedness” analysis. A finite set of luls can be regarded as a type which may be associated with a variable. Thus, a new algebra of atoms is built and substitution, unification (lub) and anti-unification (gib) operations are redefined in an easy way. Then, a general abstract resolution (called abstract OLDT resolution) based on the work of H. Tamaki and T. Sato is presented. This abstract resolution always terminates and allows the collection of some information about the concrete resolution (i. e. , the standard Prolog interpretation) of all program. The three stages for our Prolog program abstract interpretation are: 1) computation of a finite set of “significant” luls by looking into the structure of a given Prolog program. 2) abstract resolution from a given call-pattern. 3) analysis of the abstract structure (result of the previous step) for establishing properties like, e. g. , solution pattern(s), termination, boundedness, determinism, complexity, .. .