Increasing Nogoods in Restart-Based Search
Authors: Jimmy Lee, Christian Schulte, Zichen Zhu
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results confirm that our lightweight filtering algorithm and approximated nogood minimization successfully trade a slight loss in pruning for considerably better efficiency, and hence compare favorably against existing state-of-the-art techniques. Experimental Evaluation This section gives three sets of experiments to demonstrate the advantage of using inc NGs in restarts and the dynamic subscription based lightweight filtering algorithm. |
| Researcher Affiliation | Academia | Department of Computer Science and Engineering The Chinese University of Hong Kong, Shatin, N.T., Hong Kong {jlee,zzhu}@cse.cuhk.edu.hk School of ICT, KTH Royal Institute of Technology, Sweden cschulte@kth.se |
| Pseudocode | Yes | Algorithm 1 Light Filter() Require: Σ: the encoding sequence m = |Σ| α, β: the position of the two leftmost unsatisfied +ve decisions 1: Update Alpha(); ... Algorithm 2 Update Alpha() 1: if δα is satisfied then ... Algorithm 3 Update Beta() 1: if δβ is satisfied then ... Algorithm 4 Approx Constructive(P,Σ,φ) Require: Δ = : the set of transition decisions α = 1: the position of the current last -ve decision 1: P = P; 2: for i [0, |Σ| 1] do |
| Open Source Code | No | The paper does not provide an explicit statement about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | Yes | Open Shop Scheduling from the 2006 CSP Solver Competition1. ... 1http://www.cril.univ-artois.fr/ lecoutre/benchmarks.html |
| Dataset Splits | No | The paper mentions using problem instances from competitions and discusses 'failure limit' and 'solving the same problem' but does not explicitly specify data splits like percentages or sample counts for training, validation, or test sets. |
| Hardware Specification | Yes | All experiments are conducted using Gecode 4.3.2 on Intel machines with 30-45GB of memory and 64-bit Debian 6.0.6 operating system. |
| Software Dependencies | Yes | All experiments are conducted using Gecode 4.3.2 on Intel machines with 30-45GB of memory and 64-bit Debian 6.0.6 operating system. |
| Experiment Setup | Yes | The failure limit at each restart according to the Luby strategy is (1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, . . .) and we scale each element by a factor of 100. We exploit the adaptive dom/wdeg (Boussemart et al. 2004) variable ordering heuristic as a simple and yet effective generic heuristic. |