Solving the Identifying Code Set Problem with Grouped Independent Support
Authors: Anna L.D. Latour, Arunabha Sen, Kuldeep S. Meel
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section we describe our experiments aimed at evaluating the performance of gismo, comparing it to the state-of-the-art ILP-based method. ... Our benchmark set comprises 50 undirected networks ... The experiments in this section are aimed at answering the following main research questions: Q1 How many instances are solved by pbpbs and gismo? Q2 How do the solving times of pbpbs and gismo scale with k and |V |? Q3 How does the number of clause in the CNF encoding scale with k and |V |? Q4 How do the cardinalities of the solutions returned by pbpbs and gismo compare? |
| Researcher Affiliation | Academia | Anna L.D. Latour1 , Arunabha Sen2 and Kuldeep S. Meel1 1National University of Singapore, Singapore 2Arizona State University, Tempe, AZ, USA |
| Pseudocode | Yes | Algorithm 1 The gismo algorithm. Input: Formula F(Z, A) with partitioning of Z into G, a time limit τ. Output: GIS I G. |
| Open Source Code | Yes | Open-source tool, reproducibility info, and extended version of this paper are available at https://github.com/meelgroup/gismo. |
| Open Datasets | Yes | Our benchmark set comprises 50 undirected networks obtained from the Network Repository [Rossi and Ahmed, 2015] and from the Identifying Codes Git Hub repository [Basu and Sen, 2021b]. |
| Dataset Splits | No | The paper describes using a 'benchmark set' but does not specify how this set was split into training, validation, or test subsets, nor does it refer to predefined splits for reproducibility. |
| Hardware Specification | Yes | We ran our experiments on a high-performance cluster, where each node is equipped with two Intel E5-2690 v3 CPUs, each with 12 cores and 96 GB RAM, running at 2.60 GHz, under Red Hat Enterprise Linux Server 6.10. |
| Software Dependencies | Yes | Our implementation of gismo uses SAT solver Crypto Mini Sat [Soos et al., 2009] version 5.11.7... We implemented the scripts for encoding networks into CNF (Eq. (5)) or ILP (Section 3) with Python 3.5, using PBLib [Philipp and Steinke, 2015] for the CNF encoding of the cardinality constraint. We solved the ILPs with CPLEX 12.8.0.0.1. |
| Experiment Setup | Yes | Experimental parameters. We allow gismo and pbpbs each one core, 3 600 CPU s and 4 GB RAM to encode and solve each (network, k) combination. For gismo we set a time limit of τ = 5 000 conflicts for the call to Crypto Mini Sat in Line 12. For CPLEX we use the default settings. |