A MaxSAT-Based Framework for Group Testing
Authors: Lorenzo Ciampiconi, Bishwamittra Ghosh, Jonathan Scarlett, Kuldeep S Meel10144-10152
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our extensive experimental results show that MGT can solve group testing instances of 10000 items with 3% defectivity, which no prior work can handle to the best of our knowledge. |
| Researcher Affiliation | Academia | Lorenzo Ciampiconi,1 Bishwamittra Ghosh,2 Jonathan Scarlett,2 Kuldeep S Meel2 1Politecnico di Milano, 2National University of Singapore |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | 1https://github.com/meelgroup/mgt |
| Open Datasets | No | We consider Bernoulli trials (Aldridge, Johnson, and Scarlett 2019) to model a stochastic group testing instance. In particular, we consider three independent and identically distributed (i.i.d.) Bernoulli processes: an item is defective independently with probability p < 0.5, item i belongs to test j independently with probability q, and in the noisy setting, a test outcome is inverted independently with probability d < 0.5. The paper generates its own data according to these processes rather than using a publicly available dataset with concrete access information. |
| Dataset Splits | No | We repeat each experiment for l = 100 trials to ensure statistical consistency. The paper does not use standard train/validation/test splits, as it generates synthetic problem instances rather than using a fixed dataset. |
| Hardware Specification | Yes | The experiment was conducted on a machine with Intel core i7 (3.4 GHz) and 8 GB of RAM. |
| Software Dependencies | No | In our implementation, we employ Max HS (Davies and Bacchus 2011) as the underlying Max SAT solver. [...] In the LP approach, we use CPLEX as the underlying LP solver3. Version numbers for the solvers are not provided. |
| Experiment Setup | Yes | We set the cut-off time of both the LP and Max HS solvers to be 100 seconds. [...] In particular, we consider three independent and identically distributed (i.i.d.) Bernoulli processes: an item is defective independently with probability p < 0.5, item i belongs to test j independently with probability q, and in the noisy setting, a test outcome is inverted independently with probability d < 0.5. |