Robust Solutions for Constraint Satisfaction and Optimization

Abstract

1 Introduction Many decision and optimization problems contain uncertainty andthus, the user may require robust solutions. A solution is usually seen as robust if future changes are unlikely to affect it. It is difficult, how-ever, to characterize such robustness whilst taking no assumption on the likelihood of the changes themselves. We consider here a slightlydifferent definition of the notion of robustness, where the effect of certain changes on the solution can be bounded a priori. For exam-ple, when, in a scheduling problem, a machine breaks down or an activity is delayed, we would like to be able to repair it with a fewlocal changes. Super solutions are a mechanism to guarantee such solution robustness within constraint programming [10]. An (a; b)-super solution is one in which if