Super Solutions in Constraint Programming

To improve solution robustness, we introduce the concept of super solutions to constraint programming. An (a,b)-super solution is one in which if a variables lose their values, the solution can be repaired by assigning these variables with a new values and at most b other variables. Super solutions are a generalization of supermodels in propositional satisfiability. We focus in this paper on (1,0)-super solutions, where if one variable loses its value, we can find another solution by re-assigning this variable with a new value. To find super solutions, we explore methods based both on reformulation and on search. Our reformulation methods transform the constraint satisfaction problem so that the only solutions are super solutions. Our search methods are based on a notion of super consistency. Experiments show that super MAC, a novel search-based method shows considerable promise. When super solutions do not exist, we show how to find the most robust solution. Finally, we extend our approach from robust solutions of constraint satisfaction problems to constraint optimization problems.