Robust solutions for constraint satisfaction and optimization

Abstract. Super solutions are a mechanism to provide robustness to constraint programs [10]. They are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. We extend the super solution framework along several dimensions to make it more useful practically. We present the first algorithm for finding super solutions in which the repair can, if needed, change variables that have not broken. We also extend the framework and algorithms to permit a wide range of practical restrictions on the breaks and repairs (for example, repairs might have to be later in time). We also show how to deal with symmetry when finding super solutions. Symmetry is a frequent problem in constraint solving. Experimental results suggest that it is even more important to tackle symmetry when looking for super solutions. Finally, we present results on job shop scheduling problems which demonstrate the tradeoff between solution robustness and makespan. For example, we are able to return solutions which are significantly more robust with no sacrifice in the makespan.