TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models
Authors: Özgür Akgün, Ian Gent, Christopher Jefferson, Zeynep Kiziltan, Ian Miguel, Peter Nightingale, András Z. Salamon, Felix Ulrich-Oltean
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We comprehensively evaluate our approach using benchmark problems from existing literature that previously relied on manual identification by constraint programming experts of constraints to tabulate. We demonstrate that our automated identification and tabulation process achieves comparable, and in some cases improved results. We empirically evaluate the efficacy of our approach on a variety of solvers, including standard CP (Minion and Gecode), clause-learning CP (Chuffed and OR-Tools) and SAT solvers (Kissat). Our findings highlight the substantial potential of fully automated tabulation, suggesting its integration into automated model reformulation tools. |
| Researcher Affiliation | Academia | Özgür Akgün EMAIL Ian P. Gent EMAIL School of Computer Science, University of St Andrews St Andrews, Fife KY16 9SX, UK Christopher Jefferson EMAIL School of Science and Engineering, University of Dundee Dundee, DD1 4HN, UK Zeynep Kiziltan EMAIL Department of Computer Science and Engineering University of Bologna Mura Anteo Zamboni 7, 40126, Bologna, Italy Ian Miguel EMAIL School of Computer Science, University of St Andrews St Andrews, Fife KY16 9SX, UK Peter Nightingale EMAIL Department of Computer Science, University of York Heslington, York YO10 5GH, UK András Z. Salamon EMAIL School of Computer Science, University of St Andrews St Andrews, Fife KY16 9SX, UK Felix Ulrich-Oltean EMAIL Department of Computer Science, University of York Heslington, York YO10 5GH, UK |
| Pseudocode | No | The paper describes algorithms (e.g., for generating tables in Appendix B) in natural language and mathematical notation, but does not include any clearly labeled pseudocode blocks or algorithms in a structured, code-like format. |
| Open Source Code | Yes | The base models (with parameter files) are publicly available online (Akgün et al., 2024) alongside a version of Savile Row that implements Tab ID. |
| Open Datasets | Yes | The base models (with parameter files) are publicly available online (Akgün et al., 2024) alongside a version of Savile Row that implements Tab ID. We experimented with the 102 randomly-generated instances from CSPLib (Nightingale, 2018). All models and instances are available in the experiments repository. |
| Dataset Splits | No | The paper describes the use of various problem instances, some from CSPLib, some generated, and some from benchmark repositories. For example, for Black Hole, it mentions "102 randomly-generated instances from CSPLib (Nightingale, 2018)" and for Sports Scheduling Completion, "10 instances were generated with n = 12 and 10 slots assigned a team at random with uniform distribution." It evaluates performance on these instances. However, it does not specify any explicit train/test/validation splits for a single dataset, but rather treats each instance as a separate problem to be solved and evaluated. |
| Hardware Specification | Yes | Each reported time is the median of five runs on a 134-node cluster, each node having two 48-core AMD EPYC3 processors and 512 GB RAM; jobs were submitted requiring 1 CPU core and 6 GB RAM. This project was undertaken on the Viking Cluster, which is a high performance compute facility provided by the University of York. |
| Software Dependencies | Yes | Minion Version 1.9.2 of Minion (Gent et al., 2006)... Gecode Commit d1bd874 on the release/6.3.0 branch of Gecode (Gecode Team, 2024)... Chuffed Version 0.13.0 of Chuffed (Chu et al., 2018)... OR-Tools Version 9.7.2996 of OR-Tools (Perron & Didier, 2023)... Kissat Version 3.1.1 of Kissat (Biere & Fleury, 2022)... We used Savile Row 1.10.0 for the experiments, extended with the new Tab ID method. |
| Experiment Setup | Yes | For this feasibility evaluation, we do not consider the effectiveness of tabulations: in Section 6, we will show that in many cases applying Tab ID strongly improves the total time to tailor and solve an instance (including time taken to identify candidates and perform tabulation). This feasibility evaluation is divided into two. We first examine, in Section 5.1, what we call Baseline Problems where we have identified examples of tabulation in the literature. Following some preliminary experiments, we have set the parameter node Limit to 100,000 for our feasibility evaluations. Also, we chose not to apply the SAT size limit. The effect of the node limit can be seen (for example) with the Killer Sudoku problem where some constraints of arity 5 (on variables with domain size 16) fail a progress check but others are successfully tabulated. |