Research Interests

Constraint Programming

If you are able to read French, you can look at the synthesis of my HDR [pdf]. It describes all my research. It also presents constraint programming and modeling. You can also find some information in the chapter I wrote in the book of Michela Milano. This chapter is available here. This chapter contains, among some other things, some general considerations about the design of filtering algorithms and it proposes a definition of the quality of a filtering algorithm.

Global constraints and General AC Algorithms

I am the author of some well known global constraints:

I have also proposed some general algorithms to establish arc consistency.

  • In the area of binary constraints:
    I am one of the authors of AC-7, [ps] AC-Inference [ps], AC-2000 and AC-2001 [aij pdf], [ijcai ps]. Recently I introduced a new algorithm AC-* which is able to represent any AC algorithm. In this paper [english pdf], [french pdf] all of existing AC algorithms are described and the concepts on which these algorithms are based are identified. A new nomenclature for AC algorithms is also given. This new algorithm was first called CAC, but some people told me that it was not a good name, and Gilles Pesant suggested AC-* to me. I liked this name, so I thank Gilles. Some of the previous papers give results involving a MAC version of the AC algorithm (MAC stands for Maintaining Arc Consistency). MAC-4, MAC-6, MAC-7, MAC-Inference are fully detailed in my PhD thesis. Unfortunately, when I left the University of Montpellier, I lost my dissertation source files. You will find a recent paper [here] describing in detail the implementation of MAC-6 and MAC-7. In addition this paper shows that these algorithms can be implemented with the same space and time complexity as AC-6 and AC-7.
  • In the area of non binary constraints:
    GAC-Schema [ps] is a general framework for dealing with constraints that are given by the set of allowed combinations, the set of forbidden combinations, or by any predicate. This schema is able to avoid traversing the same part of a search tree search twice when entering the search tree search from different nodes. This algorithm has also been refined [ps].

Over-constrained Problems

With Thierry Petit, whom I was one of his PhD supervisors (the other one was Christian Bessière), we studied over constrained problems from a real world point of view. In other words, we looked at real world applications and then we proposed some models and original algorithms to help with their resolution:

  • A new model based on meta-constraints is described [here]. This paper formalizes and extends common ideas used in the industry to solve complex over-constraint real life applications. It also compares the new model with the Valued CSP model.
  • We have generalized the PFC-MRDAC (Partial Forward Checking Maintaining Reversible Directed Arc Consistency) algorithm to non binary constraints and proposed a new algorithm based on the concept of conflict set (that is a subset of constraints for which we detect a failure by using the propagation mechanism for instance) [english pdf], [french ps]. This paper also shows some drawbacks of the PFC-MRDAC, notably by identifying the constraints that are ignored by PFC-MRDAC. Our algorithm can be used independently of, or in conjunction with, PFC-MRDAC. It is focused on the use of the filtering algorithms associated with the constraints, even when these constraints are soft. A more detailed presentation of this idea is [here]. Some refinements of the conflict set algorithms have been made [english pdf], [french ps].
  • Range-PFC-MRDAC is a version of the PFC-MRDAC algorithm dealing only with the ranges of the variables (this is required for some scheduling applications where the domains are huge) [ps].
  • The concept of global soft constraints has been introduced for the first time in this paper [ps]. It presents the soft alldiff constraint.

Modeling and Resolution of Real World Problems

I have also worked a lot on the modeling and the resolution of real world problems:

  • A definition of what a good model is can be found [here]. This didactic paper considers a difficult problem (i.e. the minimization of the number of breaks in sports scheduling) and shows step by step how an efficient model can be defined.
  • The problem of determining the usefulness of a dedicated filtering algorithm versus the use of a general algorithm is discussed in this paper [ps].
  • A CP model for over-constrained problems is described [here].
  • A sports scheduling problem and the CP model I wrote is often used by some CP people to introduce constraint programming to the other community, like operational research. The OPL syntax of this model is available [here].
  • As example of CP applied to biology, there is a specific RNA folding problem [ps].
  • CP can also be an efficient technique to solve pure combinatorial problem as shown in this paper [pdf] which deals with the search of the maximum clique in a graph.
  • Network design is a very difficult problem. It appears that CP is one of the best methods and the most robust one for solving it [ps] [french pdf] The first paper also mentions the interesting idea of graph variables. That is, variables those domains are a subgraph of a given graph.
  • Some difficult instances of the quasi group completion problems are efficiently solved with the cardinality matrix constraint [pdf].
  • Some instances of car sequencing problems are efficiently solved with the sequence constraint [ps].

Miscellaneous

I am also an author of a paper [ps] that triggered a lot of discussions in the CSP community. This paper claims that lookahead techniques seems to be better than lookback techniques.

At last, I am a coauthor of Lazy AC [ps]. In my opinion, this is a nice algorithm. Instead of considering all the values in the domain and then removing the ones that are not consistent with the constraint, Lazy AC proposes to start from empty domains and then to add values to them until arc consistency is established. Several works in configuration are really close to this idea.

Last revised: 04/11/09