Counterfactual explanations for unsatisfiable producer/ consumer problems
Loading...
Date
2025-11-03
Authors
Dev Gupta, Sharmi
Simonis, Helmut
Quesada, Luis
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published Version
Abstract
In constraint satisfaction and constraint programming an explanation often strives to interpret the reasons for an infeasible scenario. This interpretation mostly depends on the identification of minimal conflicts (or minimal unsatisfiable subsets). Conflicts have been studied extensively in areas such as model-based diagnosis, Boolean satisfiability, product configuration, solving logic puzzles, interactive search, etc., where the user constraints play an important role [2]. For example, when solving a scheduling problem, an explanation can provide insights to why a schedule cannot be found given the set of tasks to be completed, the due-dates, and the resources available, by identifying a relaxation of the problem so that one can find a feasible schedule. Recently, the need for user-centered explanations in AI has substantially increased due to several important factors such as the black-box nature of many complex AI applications, the right to explanation of a decision in the EU’s General Data Protection Regulations, and the idea of Trustworthy AI for building trust between AI and the society. To address this issue, Wachter et al. [7] proposed to use counterfactuals and adapted them to the AI domain to explain algorithmic decisions. They describe a counterfactual explanation as a statement that explains the minimal change to the system that results in a different outcome.
Providing counterfactual explanations is expected to improve the understandability of the underlying model, and support the decision-making process of the user. A counterfactual explanation seeks to provide a minimal explanation to a question of the form: “Why is the outcome X and not Y ?”. The producer/consumer constraint [6] is a global constraint which can arise in many scenarios in scheduling or resource allocation problems. It ensures that at any time point, enough resources are available for consumption by certain tasks. The resources considered could be raw materials, finished products, or intermediate products during a continuous or discrete production process. A producer/consumer constraint on consumable resources ensures that at any time more resources must have been produced than consumed.
In many real world scenarios, enforcing a single, specific producer/consumer constraint could cause infeasibility of the complete scheduling problem. For some orders, it is not possible to satisfy the given due date simply because not enough of the required raw materials are available in time.
The operator may resolve this conflict by arranging an earlier delivery date of some raw material order, or by changing the quantity delivered. While often expensive, these relaxations would be preferable to missing the customer order due date, and paying late delivery penalties. On the other hand, the quantity of a raw material needed to produce some item typically can not be changed, sosome of the parameters of the producer/consumer constraint cannot be relaxed. The exact details of which values can be modified will depend on the specific problem instance. It is, for example, not specified quantity of paint without affecting product quality. In addition, it is also not possible to perform further operations on the painted product before it is fully dry and safe for handling. Counterfactual explanations can be used to provide solutions for these infeasible producer/-consumer constraints in a reasonable manner. Although there has been limited work on infeasible producer/consumer constraints, there is work which is relevant to our approach. Simonis and Cornelissens [6] first presented the modeling of producer/consumer constraints and its usefulness in expressing resource scheduling problems. They expressed the producer/consumer constraint using the cumulative [1] constraint, by converting the events at a time point in the cumulative constraint into tasks stretching over a time period and the constraints over resource requirement in a time period into constraints on individual time points. In other constraint solvers, the constraint can be expressed by cumul functions [4]. More recently, Schutt and Stuckey [5] have presented their work to find the most appropriate approach to explain complex scheduling problems. They extend the
producer/consumer constraint for nogood learning solvers.
In this paper, we build on our earlier approach introduced in [3], where we identified the maximal relaxation and counterfactual explanations for infeasible RCSP problems. We use that approach for finding counterfactual explanations for infeasible producer/consumer problems. This application would provide an interactive, user centric approach to first identify the exact causes for infeasibility and then providing the user with a single feasible solution closest to their original constraints.
Description
Keywords
Counterfactual explanation , Minimal exclusion set , Maximal explanation
Citation
Dev Gupta, S., Simonis, H., Quesada, L. and O'Sullivan, B. (2025) 'Counterfactual explanations for unsatisfiable producer/ consumer problems', 37th International Conference on Tools with Artificial Intelligence, Athens, Greece, 03-05 November 2025. https://doi.org/10.4230/LIPIcs.ExCoS.2025.1