Bipartite Encoding: A New Binary Encoding for Solving Non-Binary CSPs
Authors: Ruiwei Wang, Roland H.C. Yap
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on a large set of non-binary CSP benchmarks with table constraints using the Wdeg, Activity and Impact heuristics show that BE with our AC propagator can outperform existing stateof-the-art GAC algorithms (CT, STRbit) and binary encodings (HVE with HTAC). |
| Researcher Affiliation | Academia | Ruiwei Wang and Roland H.C. Yap School of Computing, National University of Singapore {ruiwei,ryap}@comp.nus.edu.sg |
| Pseudocode | Yes | Algorithm 1: BE(X,C); Algorithm 2: partition(C); Algorithm 3: max Edge(cur); Algorithm 4: AC-BE(C) |
| Open Source Code | No | The paper states: 'All algorithms are implemented in the Abscon solver (https://www.cril.univ-artois.fr/ lecoutre/#/softwares).' This provides a link to a third-party solver used for implementation, but there is no explicit statement or link indicating that the authors' specific source code for the Bipartite Encoding (BE) or AC-BE propagator is open-source or publicly available. |
| Open Datasets | Yes | We tested all 2559 non-binary instances, which only employ table constraints, from the XCSP3 website (http://xcsp.org). |
| Dataset Splits | No | The paper mentions evaluating on '2559 non-binary instances' from the XCSP3 website. While it discusses search heuristics and restart strategies, it does not specify how these instances were split into training, validation, or test sets (e.g., percentages, sample counts, or a cross-validation setup). The term 'validation' is used in the context of a function within their algorithm, not dataset partitioning. |
| Hardware Specification | Yes | The experiments were run on a 3.20GHz Intel i7-8700 machine. |
| Software Dependencies | No | The paper mentions: 'All algorithms are implemented in the Abscon solver (https://www.cril.univ-artois.fr/ lecoutre/#/softwares).' However, it does not provide a specific version number for the Abscon solver or any other programming languages, libraries, or dependencies used in the implementation or experimentation. |
| Experiment Setup | Yes | The value heuristic used is lexical value order. [...] Total CPU time is limited to 10 minutes per instance and memory to 8GB. The initial cutoff= 10 and ρ = 1.1. For each restart, cutoff is the allowed number of failed assignments and cutoff increases by (cutoff ρ) after restart. |