Efficiently Explaining CSPs with Unsatisfiable Subset Optimization
Authors: Emilio Gamba, Bart Bogaerts, Tias Guns
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We have experimentally validated our algorithms on a large number of CSP problems. We found that our algorithms outperform the MUS approach in terms of explanation quality and computational time (on average up to 56 % faster than a standard MUS approach). |
| Researcher Affiliation | Academia | Emilio Gamba EMAIL Bart Bogaerts EMAIL Vrije Universiteit Brussel, Pleinlaan 5 1050 Elsene, Belgium Tias Guns EMAIL KULeuven, Oude Markt 13 bus 5500 3000 Leuven, Belgium |
| Pseudocode | Yes | Algorithm 1: explain(C, f, I0) ... Algorithm 7: Corr Subsets(S, F) |
| Open Source Code | Yes | The code for all experiments is made available at https://github.com/ML-KULeuven/ocus-explain. |
| Open Datasets | Yes | Regarding the benchmark dataset, we rely on a set of generated Sudoku puzzles of increasing difficulty (different amount of given numbers), the Logic Grid puzzles of Bogaerts et al. (2021), as well as the instances from Espasa et al. (2021). |
| Dataset Splits | No | The paper does not explicitly provide training/test/validation dataset splits, as it evaluates on a collection of puzzle instances rather than a dataset with traditional splits for machine learning tasks. |
| Hardware Specification | Yes | Our experiments2 were run on a compute cluster where each explanation sequence was assigned a single core on a 10-core INTEL Xeon Gold 61482 (Skylake) processor with a time limit of 60 minutes and a memory-limit of 8GB. |
| Software Dependencies | Yes | The code is written on top of Py SAT 0.1.7.dev1 (Ignatiev et al., 2018). For the MIP calls, we used Gurobi 9.1.2, and for the SAT calls Mini Sat 2.2 and for Max SAT calls RC2 as bundled with Py SAT. |
| Experiment Setup | Yes | Similar to Gamba et al. (2021), for Logic Grid puzzles, we assign a cost of 60 for puzzle-agnostic constraints; 100 for puzzle-specific constraints; and a cost of 1 for facts. For all other puzzles, we assign a cost of 60 when using a constraint and a cost of 1 for facts. ... with a time limit of 60 minutes and a memory-limit of 8GB. |