Decomposition of the Factor Encoding for CSPs
Authors: Chavalit Likitvivatanavong, Wei Xia, Roland H. C. Yap
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present extensive experiments that evaluate the new FDE encoding compared with the FE and the original network. The experiments were run on a 3.20GHz Intel i7-960 with 64bit Linux. Graphs in Fig. 4 (in color) show overall performance of different techniques when all random problem instances are taken into account. Table 1 shows the mean results on unstructured problems. |
| Researcher Affiliation | Academia | Chavalit Likitvivatanavong, Wei Xia, and Roland H. C. Yap School of Computing, National University of Singapore, Singapore {chavalit,xiawei,ryap}@comp.nus.edu.sg |
| Pseudocode | Yes | We explain the process as follows. Given network P, 1. Construct fe(P) 2. (Decomposition) For each factor variable f scp(c ), (a) subtract σ(f) from scp(c ). (b) add a new constraint cf such that scp(cf) = {f} σ(f), and rel(cf) = {(t, ai1, . . . , ai|σ(f)|) | t D(f) t = (ai1, . . . , ai|σ(f)|)}. |
| Open Source Code | No | The paper does not provide a direct link or explicit statement about the availability of its source code for the described methodology. It mentions using 'Abs Con' as the solver, which is a third-party tool. |
| Open Datasets | Yes | All extensional benchmarks from the CSP solver competition1 that are non-binary and factorable are used. Footnote 1 provides the URL: Available at http://www.cril.univ-artois.fr/CSC09. |
| Dataset Splits | No | The paper does not provide explicit details about training, validation, or test dataset splits. It evaluates performance on problem instances from benchmarks, which are solved, rather than split for training and evaluation in a machine learning context. |
| Hardware Specification | Yes | The experiments were run on a 3.20GHz Intel i7-960 with 64bit Linux. |
| Software Dependencies | Yes | We used Abs Con [Merchez et al., 2001] as the solver2... We used the latest version Abs Con1.41 (not publicly available). |
| Experiment Setup | Yes | CPU time is limited to 1800 seconds while memory is limited to 8GB. We employed four well-known and commonly used variable selection heuristics in our experiments, dom/ddeg, dom/wdeg [Boussemart et al., 2004], impact [Refalo, 2004], activity [Michel and Hentenryck, 2012], and test them on the original problem as well as the FE and the FDE encodings. We used lex value ordering in all cases. |