Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Variable Elimination in Binary CSPs
Authors: Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In Section 9 we present the results of our experimental trials on 3,557 benchmark instances. The variable-elimination rules allowed us to solve more instances when they were applied in a preprocessing step, but we recommend more research to better target those variables that are likely to be eliminated before integrating these rules in a general-purpose solver. |
| Researcher Affiliation | Collaboration | Martin C. Cooper EMAIL IRIT, University of Toulouse III 31062 Toulouse, France Achref El Mouelhi EMAIL H & H: Research and Training 13015 Marseille, France Cyril Terrioux EMAIL Aix Marseille Univ, Universit e de Toulon CNRS, LIS, Marseille, France |
| Pseudocode | Yes | Appendix A. Algorithm for Variable Elimination by the DE-snake Property Appendix B. Algorithm for Variable Elimination by the Triangle Property Appendix C. Algorithm for Variable Elimination by the BT-degree Property |
| Open Source Code | No | The paper states "All the algorithms are written in C++ in our own library." but does not provide any link to a repository, an explicit statement of code release, or mention of code in supplementary materials. |
| Open Datasets | Yes | We considered all the binary instances from the 2008 International CP Competition1 and we discarded those whose inconsistency is detected by enforcing arc-consistency. By so doing, we obtained a benchmark of 3,557 CSP instances. These instances have between 3 and 5,000 variables whose initial domains have between 2 and 10,000 values. The number of constraints varies from 3 to 124,750. Constraints are de๏ฌned in extension or in intension. For example, among these instances, we can ๏ฌnd frequency allocation problems or graph colouring instances. 1. http://www.cril.univ-artois.fr/CPAI08 |
| Dataset Splits | No | The paper mentions using 3,557 benchmark instances from the 2008 International CP Competition but does not provide any specific details about training, validation, or test splits. It directly evaluates on these instances for solving efficiency. |
| Hardware Specification | Yes | The experiments were performed on Dell Power Edge M620 blade servers with Intel Xeon E52609 2.4 GHz processors. |
| Software Dependencies | No | The paper mentions that "All the algorithms are written in C++ in our own library." and refers to "MAC+RST+NG (Lecoutre, Sais, Tabary, & Vidal, 2007)" and "dom/wdeg variable heuristic (Boussemart, Hemery, Lecoutre, & Sais, 2004)". However, it does not specify version numbers for C++, the library, or any other software components used. |
| Experiment Setup | Yes | We exploit a geometric restart policy based on the number of allowed backtracks. Initially, the number of allowed backtracks is set to 100 and the increasing factor to 1.1. The search was guided by the dom/wdeg variable heuristic (Boussemart, Hemery, Lecoutre, & Sais, 2004). All the algorithms are written in C++ in our own library. The experiments were performed on Dell Power Edge M620 blade servers with Intel Xeon E52609 2.4 GHz processors. We allotted 30 minutes and 16 GB of memory for each elimination process while, for the solving process, the timeout was set to one hour. |