• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
A MaxSAT-based Framework for Group Testing.
Lorenzo Ciampiconi, Bishwamittra Ghosh, Jonathan Scarlett and Kuldeep S. Meel.
In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), February 2020.
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 ap- proach. We also discover an interesting phase transition behavior in the runtime, which reveals the easy-hard-easy nature of group testing.
@inproceedings{CGSM20,
author={
Ciampiconi, Lorenzo and Ghosh, Bishwamittra and Scarlett, Jonathan and Meel,
Kuldeep S.
},
title={A {MaxSAT}-based Framework for Group Testing},
booktitle=AAAI,
month=feb,
year={2020},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={../Papers/aaai20-cgsm.pdf},
code={https://github.com/meelgroup/mgt},
bib2html_rescat={Formal Methods 4 ML},
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 ap- proach. We also discover an
interesting phase transition behavior in the runtime,
which reveals the easy-hard-easy nature of group testing.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Thu Apr 30, 2026 09:22:03