Early and Efficient Identification of Useless Constraint Propagation for Alldifferent Constraints
Authors: Xizhe Zhang, Jian Gao, Yizhi Lv, Weixiong Zhang
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our implementation of the new method achieved speedup by a factor of 1 to 5 over the state-of-art approaches on 93 benchmark problem instances in 8 domains. Besides, the new algorithm is scalable well and runs increasingly faster than the existing methods on larger problems. |
| Researcher Affiliation | Academia | Xizhe Zhang1,3, Jian Gao2, Yizhi Lv3 and Weixiong Zhang4 1School of Biomedical Engineering and Informatics, Nanjing Medical University, Nanjing, China 2College of Information Science and Technology, Dalian Maritime University, Dalian, China 3School of Computer Science and Engineering, Northeastern University, Shenyang, China 4Department of Computer Science and Engineering, Washington University, St. Louis, MO, USA |
| Pseudocode | Yes | Algorithm 1: Find SCCs With Early Detection |
| Open Source Code | No | The paper states 'We used Minion constraint solver 1.8 [Gent et al., 2006] to implement our algorithm.' and provides links to third-party tools (Minion, CSPLib, Conjure, Savile Row), but does not explicitly state that the authors' own implementation code is open-sourced or provide a link to it. |
| Open Datasets | Yes | The benchmark problems for valuation were from the CSP Lib (http://www.csplib.org/) and Minion constraint solver (https://constraintmodelling.org/minion/), which include several typical alldifferent constraint problems. These problems including Langford s number problem (prob024 in CSPLib), Golomb ruler problem (prob006 in CSPLib), Quasigroup existence (prob003 in CSPLib), Social golfers (prob010 in CSPLib), Graceful graphs (prob053 in CSPLib), Magic Squares (prob019 in CSPLib), N-Queens (prob054 in CSPLib) and Sports scheduling (prob026 in CSPLib). |
| Dataset Splits | No | The paper discusses solving constraint satisfaction problems using benchmark instances but does not describe explicit training, validation, and test dataset splits as typically found in machine learning contexts. |
| Hardware Specification | Yes | All experiments were run on a Windows 10 workstation with an Intel Xeon E5-2680 v2 processor of 2.8 GHz and 16GB DDR3 1600MHz RAM. |
| Software Dependencies | Yes | We used Minion constraint solver 1.8 [Gent et al., 2006] to implement our algorithm. |
| Experiment Setup | Yes | We adopted the depth-first chronological backtracking as the search strategy. |