Filippo Bistaffa, 

Juan Antonio Rodríguez-Aguilar

Decision Support Systems (DSS) based on optimisation techniques are widely deployed to support decision-making in complex environments. Although optimisation approaches are often perceived as more transparent than machine learning models, their outcomes (i. e. , the recommendations that will inform the decision-making process) remain difficult for non-expert users to understand. This drawback stems from the inherent complexity of real-world optimisation problems, which often involve many variables and constraints. As a result, users may struggle to understand why a particular decision is optimal, hindering their trust in and adoption of such decisions. For optimisation-based DSS to be effectively integrated into practice, providing clear explanations of their outcomes is fundamental. However, in contrast to the abundant work in explainable AI for machine learning models, considerably less research has been devoted to explainability methods for optimisation approaches. This thesis addresses this research gap by proposing a general, domain-independent approach that combines constraint reasoning techniques with Large Language Models (LLMs) to generate explanations for optimisation-based DSS. Our proposed approach enables users of optimisation-based DSS to pose questions about their recommendations. To answer such questions, which suggest alternative decisions to the DSS's outcome, our approach generates textual explanations by identifying the reasons why the optimal decision is preferable to the user-suggested alternative. Specifically, we exploit constraint reasoning techniques to structure and semantically characterise the information required by the LLM, which we then use to generate a textual explanation that answers the user's question. Since this thesis develops a general explainability approach for optimisation-based decision support systems, we tackle three novel and challenging optimisation problems across distinct real-world domains. Specifically, we consider these problems because (i) they are novel and have not previously been formalised as optimisation tasks, and (ii) they serve as diverse case studies for evaluating the proposed explainability approach. First, we formalise Value System Aggregation as an optimisation problem that aims to derive a consensus value system from a set of individual value systems. Second, we tackle the Research Project Planning Problem, which aims to find the optimal allocation of researchers' dedication to research projects. Third, we formulate the Bachelor's Degree Planning Problem as a scheduling problem, whose goal is to find a degree plan, i. e. , an allocation of university subjects across semesters, that maximises the acquisition of skills required for students' preferred jobs. These problems belong to different families of optimisation problems, namely aggregation, resource allocation, and scheduling, thereby demonstrating the generality of the proposed explainability approach. More specifically, we thoroughly evaluate our explainability approach in terms of (i) completeness, that is, the ratio of identified reasons mentioned in a textual explanation, and (ii) readability, which represents the difficulty of understanding an explanation. Furthermore, we evaluate the cost of generating explanations by applying our approach to two additional hard benchmark problems from the combinatorial optimisation literature: the Resource-Constrained Project Scheduling Problem and the Winner Determination Problem. The empirical evaluation on real-world datasets demonstrates that the proposed methodology generates complete explanations without increasing the difficulty in understanding across diverse optimisation domains. Specifically, providing the structured necessary information as input to an LLM substantially improves the completeness of the resulting textual explanations. Moreover, experimental results indicate that explanations can typically be generated in real time, often in a few seconds.