Perturbed Message Passing for Constraint Satisfaction Problems
Authors: Siamak Ravanbakhsh, Russell Greiner
JMLR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results on random and real-world CSPs show that Perturbed BP is often more successful and at the same time tens to hundreds of times more efficient than standard BP guided decimation. |
| Researcher Affiliation | Academia | Department of Computing Science University of Alberta Edmonton, AB T6E 2E8, CA |
| Pseudocode | Yes | Algorithm 1: Belief Propagation-guided Decimation (BP-dec) Algorithm 2: Perturbed Belief Propagation |
| Open Source Code | No | The paper states: We implemented all the methods above for general factored CSP using the libdai code base (Mooij, 2010). This indicates the use of a third-party tool, not that the authors' specific implementation for the paper's methodology is open-sourced. |
| Open Datasets | Yes | We considered CSP instances from XCSP repository (Roussel and Lecoutre, 2009; Lecoutre, 2013) |
| Dataset Splits | No | The paper discusses using '100 random instances' for evaluation and benchmark CSP instances from the XCSP repository. However, it does not provide details on training/test/validation splits in the context of machine learning, as the algorithms are applied to solve individual problem instances rather than trained on a dataset to learn a model. |
| Hardware Specification | No | This research has been enabled by the use of computing resources provided by West Grid and Compute/Calcul Canada. This refers to general computing infrastructure but does not specify particular CPU or GPU models, memory, or detailed computer specifications. |
| Software Dependencies | No | We implemented all the methods above for general factored CSP using the libdai code base (Mooij, 2010). While it mentions 'libdai', it does not provide a specific version number for the software. |
| Experiment Setup | Yes | We used a convergence threshold of ϵ = .001 for BP and terminated if the threshold was not reached after T = 10 210 = 10, 240 iterations. To perform decimation, we sort the variables according to their bias and fix ρ fraction of the most biased variables in each iteration of decimation. This fraction, ρ, was initially set to 100%, and it was divided by 2 each time BP-dec failed on the same instance. ... For Perturbed BP, we set T = 10 at the starting attempt, which was increased by a factor of 2 in case of failure. ... For BP-dec and SP-dec, we use a convergence threshold of ϵ = .001 and fix ρ = 1% of variables per iteration of decimation. Perturbed BP and Perturbed SP use T = 1000 iterations. |