Using Certifying Constraint Solvers for Generating Step-wise Explanations (Extended version)

Ignace Bleukx, Maarten Flippo, Bart Bogaerts, Emir Demirović, Tias Guns · 2025

Read Using Certifying Constraint Solvers for Generating Step-wise Explanations (Extended version) by Ignace Bleukx, Maarten Flippo, Bart Bogaerts, Emir Demirović, Tias Guns (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10428.txt.

Introduction

Ignace Bleukx and four co-authors study how to explain, step by step, why a constraint problem has no solution. Step-wise explanations show one small reasoning step at a time, each tied to the original rules, until the conflict becomes clear. Computing such sequences from scratch is expensive, which limits the size of problems they can handle.

Their idea is to reuse the proof that a certifying solver already produces while solving. They define abstract proofs, a shared format that can hold both solver proofs and explanation sequences. Conversion methods then trim and simplify the proof into a short explanation. The result is much faster generation, with explanation quality close to the best existing methods.

Catalog record

CREATORIgnace Bleukx, Maarten Flippo, Bart Bogaerts, Emir Demirović, Tias Guns
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-10428

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Using Certifying Constraint Solvers for Generating Step-wise Explanations (Extended version) Ignace Bleukx, Maarten Flippo, Bart Bogaerts, Emir Demirović, Tias Guns Abstract In the field of Explainable Constraint Solving, it is common to explain to a user why a problem is unsatisfiable. A recently proposed method for this is to compute a sequence of explanation steps. Such a step-wise explanation shows individual reasoning steps involving constraints from the original specification, that in the end explain a conflict. However, computing a step-wise explanation is computationally expensive, limiting the scope of problems for which it can be used. We investigate how we can use proofs generated by a constraint solver as a starting point for computing step-wise explanations, instead of computing them step-by-step. More specifically, we define a framework of abstract proofs, in which both proofs and step-wise explanations can be represented. We then propose several methods for converting a proof to a step-wise explanation sequence, with special attention to trimming and simplification techniques to keep the sequence and its individual steps small. Our results show our method significantly speeds up the generation of step-wise explanation sequences, while the resulting step-wise explanation has a quality similar to the current state-of-the-art. 1 Introduction The ultimate goal of declarative problem solving is that users should be able to specify a problem declaratively (i.e., they only need to specify what their problem is, not how to solve it), and can then use a generic solver to find solutions to their problem. Over the last decades, solvers have become increasingly powerful, allowing them to solve complex, real-world problems with thousands of variables and constraints. However, due to this complexity, explaining to a human why a solver produced a particular answer is still a challenge. Explanations Many types of user-oriented explanations have been developed for constraint programming ( 16 ) . We focus on explanations for problems that do not admit a solution. More specifically, we focus on methods that explain “why” the problem is unsatisfiable. A popular method is to extract a Minimal Unsatisfiable Subset (MUS) of the input constraints, which allows the user to focus on a problematic subset of the problem specification ( 24 ) . One issue, however, is that such an MUS can still be very large and hence hard to understand for a user. To better explain the interaction between constraints, and building on old ideas ( 30 ) , a framework of step-wise explanations was introduced by 6 . In this context, an explanation is a sequence of simple steps, where each step is a simple derivation based on some of the constraints specified by the user. While the framework was originally conceived to explain satisfiable (puzzle) problems, it has also been used later to step-wise explain unsatisfiability and optimality ( 5 ) . A major challenge in the computation of step-wise explanations is how to efficiently find a short sequence of small explanation steps. Despite novel algorithms designed exactly for this purpose ( 12 ) , generating a step-wise explanation remains computationally very expensive . Indeed, current approaches rely on multiple calls to an NP-oracle for computing even a single explanation step, and many more so for computing the entire sequence. The high runtime of existing approaches limits the general application of step-wise explanation methods. Our goal is to reduce the computational effort for computing a step-wise explanation sequence, by starting from a solver-generated proof instead of constructing it step-by-step. Proof Logging While combinatorial optimization tools are often used as reliable components in larger systems, their results may not always trustworthy. Indeed, there have been numerous reports of solvers reporting faulty answers ( 7 , e.g.,) . The question that naturally arises is: How can we be sure that the answer of a solver is correct? More specifically, if a solver claims that a problem is unsatisfiable or that a solution is optimal, how can we know this is indeed the case? One way to provide such a guarantee is to develop certifying algorithms ( 25 ) , which is also known as proof logging in the context of combinatorial optimization. The core idea is that solvers provide a proof of correctness of their answer. This approach has been applied very successfully in SAT, with DRAT being the dominant proof logging format ( 33 ) . Recently, proof logging has also found its way to other combinatorial solving formalisms, including MaxSAT ( 32 ; 3 ; 2 ; 31 ) , pseudo-Boolean optimization ( 19 ; 18 ) and CP ( 10 ; 14 ) . Goal: Computing Step-wise Explanations from Proofs There are several similarities, but also some crucial differences between proofs generated by certifying solvers and a step-wise explanation sequence . These differences arise because proofs are designed to be machine-verifiable , while step-wise explanations are designed to be human-interpretable . Both concepts explain the explanandum through a chain of relatively simple steps. However, in proofs, these small steps derive new, potentially complex constraints (e.g., a long clause) that can be reused as part of later proof steps. In contrast, in a step-wise explanation, each step derives a simple fact , such as a value assignment of a decision variable by only combining a few constraints specified by the user and previously derived facts ( 11 ) . Hence, solver-generated proofs do not directly provide a user-oriented step-wise explanation. Another important difference is how they are generated. Since proofs are generated efficiently during the solving process, a natural question is whether one can reuse such a proof to generate a step-wise explanation sequence . In this paper, we do exactly that and contribute the following: • We propose a general framework for unsatisfiability proofs that captures both proofs and explanations ; • we propose a suite of techniques which allow to efficiently extract a step-wise explanation from a proof, with extra attention to minimization techniques that keep the step-wise explanations small (and comprehensible) and; • we evaluate our approach on several application domains, showing our approach computes step-wise explanations up to 100 times faster, with a limited effect on the length of the explanation and its individual steps. 2 Background A Constraint Satisfaction Problem (CSP) is a triple (\mathcal{X},\mathcal{D},\mathcal{C}) with \mathcal{X} a set of integer variables \mathcal{D} a set of domains (one for each variable), and \mathcal{C} a set of constraints ( 28 ) . When the set of variables and domains is clear from the context, we write \mathcal{C} instead of (\mathcal{X},\mathcal{D},\mathcal{C}) . Boolean variables are represented as 0-1 integer variables. A constraint in this paper is any Boolean expression over \mathcal{X} , which maps variable assignments to true or false, and is written as a mathematical expression. E.g., x+y\leq 3 and (x=3)\vee(y\geq 2) both represent a constraint. Variables that occur in the arguments of a constraint are said to be in the constraint’s scope . We write \mathit{scope}(c) to denote the set of variables occurring in c . The scope trivially generalizes to sets of constraints. An assignment \alpha satisfies a constraint when the constraint maps it to true. An assignment that satisfies every constraint in \mathcal{C} is a solution of the CSP. If no solution to the CSP exists, it is said to be unsatisfiable

Read the complete text