Evaluating the Impact of Explanations on the Performance of an Edge-Finding Propagator
R.A. Vasile (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Emir Demirović – Mentor (TU Delft - Algorithmics)
I.C.W.M. Marijnissen – Mentor (TU Delft - Algorithmics)
Stephanie Wehner – Graduation committee member (TU Delft - QID/Wehner Group)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Explanations have been shown to significantly increase the performance of propagators, when applied to solvers that make use of Lazy Clause Generation. However, to date, there has been little work in exploring explanations for the disjunctive constraint and how they perform compared to simple propagation making use of Naive Explanations. I address this gap by considering an Edge-Finding propagation algorithm for the disjunctive and evaluating the performance of three variants of a solver on job-shop problems, each of them using different explanation techniques, which have been adapted from previous work. I also provide an algorithm serving as an extension to Edge-Finding, which can be used to generate explanations. Then, I compare all approaches in relation to a baseline consisting of a solver that has no support for the disjunctive and uses decomposition. Through experiments, I demonstrate that good explanations provide a significant improvement in terms of recorded metrics compared to the naive method, even if generating them requires additional computational overhead.