Dancing with Decision Diagrams: A Combined Approach to Exact Cover
Authors: Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments confirm that the proposed method is up to several orders of magnitude faster than DLX. and We conduct experiments with a wide range of benchmark instances of exact cover problems, and confirm that our proposal is up to several orders of magnitude faster than DLX. |
| Researcher Affiliation | Collaboration | 1NTT Communication Science Laboratories, NTT Corporation 2Graduate School of Information Science and Technology, Hokkaido University |
| Pseudocode | Yes | Algorithm 1: Knuth s algorithm DLX. and Algorithm 2: Algorithm DXZ. |
| Open Source Code | No | The paper states 'Algorithms were implemented in C++.' but does not provide any link or explicit statement about the availability of their source code. |
| Open Datasets | Yes | Exact cover benchmark dataset used in (Junttila and Kaski 2010)3 contains several artificial exact cover problems. The dataset is available at http://www.tcs.hut.fi/ tjunttil/experiments/CP2010/ and We also used the set partitioning problem benchmark instances available at OR-LIBRARY4. |
| Dataset Splits | No | The paper deals with combinatorial problems (exact cover) and does not involve typical machine learning dataset splits (training, validation, test) for model training or evaluation. It uses benchmark problem instances as input. |
| Hardware Specification | Yes | Experiments were conducted on a Linux machine with a Xeon E5-2687W 3.10 GHz CPU and 128 GB RAM. |
| Software Dependencies | No | The paper states 'Algorithms were implemented in C++.' but does not provide specific version numbers for any libraries, compilers, or other software dependencies used in their implementation. |
| Experiment Setup | Yes | We set the sizes of memo cache used in DXZ and its fixed ordered version to 32 MBytes, where every memo cache entry is represented by a pair of a 192-bit (24 Bytes) column ID vector and an 8 Byte pointer indicating a ZDD node (total 32 Bytes) and the memo cache table has 2^20 = 1M entries. |