Robust Solutions for Constraint Satisfaction and Optimization

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Student Abstracts

Supersolutions 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 stress the need to extend the super solution framework along several dimensions to make it more useful practically. We demonstrate the usefulness of those extensions on an example from jobshop scheduling, an optimization problem solved through constraint satisfaction. In such a case there is indeed a trade-off between optimality and robustness, however robustness may be increased without sacrificing optimality.