A MaxSAT-Based Framework for Group Testing


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




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.




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



AAAI Technical Track: Reasoning under Uncertainty