Solving Set Cover and Dominating Set via Maximum Satisfiability
Authors: Zhendong Lei, Shaowei Cai1569-1576
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiment results on a broad range of large scale instances of SCP and DSP show that our algorithm significantly outperforms state of the art solvers for SCP, DSP and Max SAT. |
| Researcher Affiliation | Academia | State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences School of Computer and Control Engineering, University of Chinese Academy of Sciences |
| Pseudocode | Yes | Algorithm 1: Dom SAT Algorithm |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code for the described methodology, nor does it include a link to a code repository. |
| Open Datasets | Yes | The first benchmark (OR-Library) (Beasley 1990)... The second benchmark (Rail)1... The third benchmark (STS) (Fulkerson, Nemhauser, and Trotter 1974)... Moreover, we consider the 65 massive real world graphs from (Wang et al. 2018) as DSP instances. |
| Dataset Splits | No | The paper uses existing benchmarks (OR-Library, Rail, STS, Wang et al. 2018 graphs) and refers to them as 'instances' of SCP and DSP problems. It does not provide specific train, validation, or test dataset split information or describe the data partitioning methodology used for these benchmarks. |
| Hardware Specification | Yes | Our experiments were conducted on a server using Intel Xeon E7-8850 v2 @2.30GHz, 2048GB RAM, running Ubuntu 16.04.5 Linux operation system. |
| Software Dependencies | No | Dom SAT is implemented in C++ and compiled by g++ with -O3 option. The paper mentions the programming language and compiler but does not specify their version numbers or any other software dependencies with versions. |
| Experiment Setup | Yes | Each solver is executed 10 times on each instance with different seeds. The time limit of all algorithms is 1000 seconds on all benchmarks except OR instances. For OR instances, the time limit of all algorithm is 10 seconds. |