Counterfactual Explanation Through Constraint Relaxation

Interactive constraint systems often suffer from infeasibility (no solution) due to conflicting user constraints. A common approach to recover feasibility is to eliminate the constraints that cause the conflicts in the system. This approach allows the system to provide an explanation as: 'if the user is willing to drop some of their constraints, there exists a solution'. However, this form of explanation might not be very informative. A counterfactual explanation is a type of explanation that can provide a basis for the user to recover feasibility by helping them understand what changes can be applied to their existing constraints rather than removing them. We propose an iterative method based on conflict detection and maximal relaxations in over-constrained constraint satisfaction problems to help compute a counterfactual explanation. We have evaluated our approach using well known instances that occur in industrial applications and demonstrated the relevance of multi-point relaxations.