A MaxSAT-Based Framework for Group Testing

Authors

  • Lorenzo Ciampiconi Politecnico di Milano
  • Bishwamittra Ghosh National University of Singapore
  • Jonathan Scarlett National University of Singapore
  • Kuldeep S Meel National University of Singapore

DOI:

https://doi.org/10.1609/aaai.v34i06.6574

Abstract

The success of MaxSAT (maximum satisfiability) solving in recent years has motivated researchers to apply MaxSAT solvers in diverse discrete combinatorial optimization problems. Group testing has been studied as a combinatorial optimization problem, where the goal is to find defective items among a set of items by performing sets of tests on items. In this paper, we propose a MaxSAT-based framework, called MGT, that solves group testing, in particular, the decoding phase of non-adaptive group testing. We extend this approach to the noisy variant of group testing, and propose a compact MaxSAT-based encoding that guarantees an optimal solution. 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. Furthermore, MGT has better accuracy than the LP-based approach. We also discover an interesting phase transition behavior in the runtime, which reveals the easy-hard-easy nature of group testing.

Downloads

Published

2020-04-03

How to Cite

Ciampiconi, L., Ghosh, B., Scarlett, J., & Meel, K. S. (2020). A MaxSAT-Based Framework for Group Testing. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10144-10152. https://doi.org/10.1609/aaai.v34i06.6574

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty