Research Interests
Solution Robustness: - PhD thesis.
When dealing with real world problems, efficiency and optimality may not be the only concerns. For instance, the most tightly optimised schedule may not be the best one if a single activity being delayed causes all other activities to stand idle. Moreover, in many cases it is difficult or even impossible to obtain a perfect matching between the real situation being modelled and the mathematical model. The real problem may simply be too complex, and no perfectly accurate model can be produced; some data may be unavailable or erroneous; the environment may simply be inherently dynamic, hence the model cannot easily capture more than agiven fixed state, etc. All these cases, from the modelling and solving viewpoint, will result in a gap between the mathematical model and the actual state of the environment when the solution is deployed.
Different methods have therefore been developed to tackle this problem (Dynamic / Flexible / Stochastic CSPs) leading to a certain robustness. Our work focuses on the notion of fault tolerance, or stability: a solution should be robust on changes, in other words, a small amount of changes should be repaired by a proportional amount of work. Supermodels (Supermodels and Robustness (Ginsberg, Parkes, Roy)) ensure exactly this property, if a certain number of atoms of a supermodel are flipped, this solution still satisfies the clauses by flipping another number of atoms. We (Brahim Hnich, Toby Walsh and myself), study this notion in CSPs and explore the ways to efficiently solve the induced problem. This work is undertaken within the MIMIC project .
Reformulation of CSP into SAT: - Master degree dissertation.
Propositional Satisfiability (SAT) and Constraint Satisfaction Problems (CSPs) are two very typical NP-complete combinatorial problems. There has been considerable research in developing algorithms for both problems. Translation from one problem to the other can therefore be valuable to either side. Enforcing a local consistency is one of the most important aspect of systematic search algorithms. In particular, arc consistency is often the best tradeoff between the amount of pruning and the cost of pruning. The AC encoding has the property that arc consistency in the original CSP is established by unit propagation in the encoding (Arc Consistency in SAT (Ian P. Gent)). A complete backtracking algorithm with unit propagation, such as DLL, therefore explores an equivalent search tree to a CSP algorithm that maintains arc consistency. This work shows that other consistencies (Relational (i,j)-consistencies) can also be simulated by unit propagation in a Davis-(Putnam)-Loveman-Logeland procedure.
Global Constraint, Complexity and Implementations: - Joint work with Christian Bessiere, Brahim Hnich, Zeynep kiziltan, Nina Narodytska, Claude-Guy Quimper and Toby Walsh.
We are interested in using computational complexity tools to study global constraints. Indeed, the complexity of a constraint dictates what level of consistency can be achieved, and to some extent what algorithmic are applicable. We analysed the (parameterised) complexity of a number of constraints (NValue, UsedBy, ScalarProduct, etc...), and introduced filtering algorithms for some of them.
In a related line of research, we proposed Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We designed specialised propagation algorithms for these two patterns. Hence, the counting and occurrence constraints specified using these patterns directly inherit a polynomial propagation algorithm. To illustrate the capabilities of the Range and Roots constraints, we specified a number of global constraints taken from the literature.
Diversity and Similarity: - Joint work with Brahim Hnich, Barry O'Sulliven and Toby Walsh
We are interested on problems where we wish to find a set of solutions which are diverse or similar to each other. Finding diverse or similar solutions can be useful in a wide range of situations. We identified a number of useful diversity and similarity problems within a constraint programming framework. We analysed their computational complexities and introduced a number of practical solution methods.
Efficient Hybrid Algorithms for the Timetabling Problem: - Joint work with Hadrien Cmabazard, Barry O'Sulliven and Alexandre Papadopoulos
We entered and won track 2 of the second international Timetabling Competition, held alongside the 7th International conference on Practice And Theory of Automated Timetabling (PATAT’07).
