Fast and Parallel Decomposition of Constraint Satisfaction Problems
Authors: Georg Gottlob, Cem Okulmus, Reinhard Pichler
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We performed our experiments on the Hyper Bench benchmark, with the goal to determine the exact generalized hypertree width of all instances. |
| Researcher Affiliation | Academia | Georg Gottlob1,2 , Cem Okulmus2 and Reinhard Pichler2 1University of Oxford, UK 2TU Wien, Austria |
| Pseudocode | Yes | Algorithm 1: Parallel Balanced Separator algorithm |
| Open Source Code | Yes | The source code of the program is available under https://github.com/cem-okulmus/Balanced Go. |
| Open Datasets | Yes | We performed our experiments on the Hyper Bench benchmark, with the goal to determine the exact generalized hypertree width of all instances. We evaluated how our approach compares with existing attempts to compute the ghw, and we investigated how various heuristics and parameters prove beneficial for various instances. The detailed results of our experiments1, in addition to the source code of our Go programs2 are publicly available. Together with the benchmark instances, which are detailed below and also publicly available, this ensures the reproducibility of our experiments. Hyper Bench. The instances used in our experiments are taken from the benchmark Hyper Bench, collated from various sources in industry and the literature, which was released by [Fischl et al., 2019] and made publicly available at http://hyperbench.dbai.tuwien.ac.at. |
| Dataset Splits | No | The paper describes using the Hyper Bench benchmark for evaluation but does not specify train/validation/test splits for their own experimental setup. |
| Hardware Specification | Yes | Our experiments ran on a cluster of 12 nodes, running Ubuntu 16.04.1 LTS with a 24 core Intel Xeon E5-2650v4 CPU, clocked at 2.20 GHz, each node with 160 GB of RAM. |
| Software Dependencies | Yes | We used Go 1.2 for our implementation, called Balanced Go. |
| Experiment Setup | Yes | For the experiments, we set a number of limits to test the efficiency of our solution. For each run, consisting of the input (i.e., hypergraph H and integer K) and a configuration of the decomposer, we set a one hour (3600 seconds) timeout and limit available RAM to 1 GB. |