ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Robust Solutions for Constraint Satisfaction and Optimization

Emmanuel Hebrard, Brahim Hnich, Toby Walsh

Super solutions are a mechanism to provide solution robustness within constraint programming. Super solutions 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. In this paper, we extend the super solution framework in several dimensions to make it more useful practically. We present the first algorithm for finding super solutions in which the repair changes both variables that have lost values and those that have not. We then extend the framework and algorithms to permit a wide range of practical restrictions on the breaks and repairs. Consider, for example, a scheduling problem in which the variables are jobs and the values are the times. We might only be able to repair a variable with a larger value as repairing with a smaller value take us back in time. We also show how to deal with symmetry when finding super solutions. Symmetry is a frequent problem in constraint solving. Our 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.

Keywords: Constraint Programming, Constraint Satisfaction, Reasoning under Uncertainty

Citation: Emmanuel Hebrard, Brahim Hnich, Toby Walsh: Robust Solutions for Constraint Satisfaction and Optimization. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.186-190.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).