XCP-explain

Explainable Constraint Solving - A Hands-On Tutorial

Authored by Ignace Bleukx, Dimos Tsouros and Tias Guns

Tutorial at the 26th European Conference on Artificial Intelligence (ECAI 2024)

Tutorial date and time

Saturday, 19 October 2024, 14:00, Room: TBA

Abstract

Explainable constraint solving is concerned with explaining constraint (optimization) problems and their solutions. While having roots in the well-studied topic of explaining unsatisfiability, it is getting renewed attention as part of the wider eXplainable AI (XAI) field. This raises new challenges in terms of interpretability and actionability of explanations, as well as algorithmic challenges with regard to scalability, expressivity, and preferences that must be considered.

We recognise two general types of explanations in XCP: deductive and contrastive explanations. We provide a deeper view of techniques in these categories, including well-established techniques like minimal unsatisfiable subsets and correction subsets, as well as newer approaches such as step-wise explanations, feasibility corrections, inverse optimization techniques, and more. The tutorial will be hands-on, being supported by working implementations on top of the CPMpy library. All techniques will be showcased using live demo’s and hands-on experimentation on nurse rostering problems in Python notebooks. This tutorial includes an introduction to constraint solving as well as general XAI, so no previous knowledge is required.

Presenters

Ignace Bleukx is a 3rd year PhD student at KU Leuven and a key developer of the CPMpy library which he presented in a tutorial at IJCAI 2022. His PhD centers around explainable constraint solving with a special interest in explaining optimization problems.

Dimos Tsouros is a PostDoc at the DTAI KU Leuven lab. His expertise is in interactive constraint acquisition, earning an honorable mention in the Doctoral Dissertation Award of ACP in 2022. He has a strong interest in rich interactive techniques between users and solvers, focusing on a more human-aware approach to the solving process.

Prof. Tias Guns works at the intersection of constraint solving, machine learning and explainable AI. With his prestigious ERC Consolidator grant on "Conversational Human-aware Technologies for Optimisation" he is pushing the boundaries of what can be done at the intersection of these fields. His team develops the Constraint Programming and Modeling library CPMpy, which serves as a core technology to investigate new ways of integrating ML and constraint solving through decision focussed learning, and explanation techniques for constraint solving through explainable CP.

Tutorial Repository

The following repository contains the code and runnable notebook for our Explainable Constraint Solving tutorials and talks: https://github.com/CPMpy/XCP-explain