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 .

Here are the slides of the talk that I gave at our "Theme" workshop in 2013. This presentation is based on the following papers, and on some unpublished results in my thesis as well as material from Alan Holland's and Victor Muñoz' thesis.