ASP for Anytime Dynamic Programming on Tree Decompositions
Authors: Bernhard Bliem, Benjamin Kaufmann, Torsten Schaub, Stefan Woltran
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We implemented both alternatives and provide an experimental evaluation on several problem encodings using realworld graphs. The multi-shot approach turns out to have clear advantages. We also demonstrate that the performance of our new lazy algorithm is typically superior to the traditional eager approach. Finally, we compare our algorithm to the state-of-the-art ASP system clingo and show that on some problems our system performs better in an anytime setting. |
| Researcher Affiliation | Academia | 1 TU Wien, Vienna, Austria 2 University of Potsdam, Germany 3 INRIA Rennes, France |
| Pseudocode | Yes | Algorithm 1: Main program; Algorithm 2: next Row; Algorithm 3: activate Next; Algorithm 4: call Child |
| Open Source Code | Yes | All instances and problem encodings are available at http://dbai.tuwien.ac.at/proj/dflat/lazy-experiments.tar.gz. |
| Open Datasets | Yes | All instances and problem encodings are available at http://dbai.tuwien.ac.at/proj/dflat/lazy-experiments.tar.gz. |
| Dataset Splits | No | The paper mentions using 11 real-world graphs as input and running 30 different random seeds per instance, but it does not specify any training, validation, or test dataset splits. The evaluation is performed on entire graph instances. |
| Hardware Specification | Yes | The benchmarks ran on a Debian GNU/Linux system (kernel 3.16.0.4) on an Intel Xeon E5345 CPU at 2.33 GHz, using only one core without hyperthreading. We limited each run to 1 GB of main memory and 10 minutes of CPU time. |
| Software Dependencies | Yes | We used the D-FLAT system with eager evaluation as well as our lazy evaluation algorithm (denoted by eager and lazy, respectively), and for lazy we tested both the re-grounding and the assumption-based approach. Moreover, we compared lazy against the ASP system clingo 4.5.4 |
| Experiment Setup | Yes | We limited each run to 1 GB of main memory and 10 minutes of CPU time. |