Optimal Combinatorial Testing with Constraints: The Balancing Act
Published in arXiv preprint arXiv:2607.17083, 2026
Thiago Serra, Changkun Guan, Hunter Gehman, Sumit Dhar, Mikey Ferguson, John Hooker, Marcel Schoppers. "Optimal Combinatorial Testing with Constraints: The Balancing Act." arXiv preprint arXiv:2607.17083, 2026.
Testing a system with many on-off components exhaustively is prohibitive, but most bugs can be isolated to interactions among few components — so test suites covering every pairwise configuration are a practical foundation. The problem goes from easy to NP-hard as soon as some pairwise configurations are forbidden.
This paper revisits unconstrained combinatorial testing with pairwise coverage on binary parameters and contrasts it with the constrained case, showing and conjecturing properties that either are upheld or change between the two — in particular, the extent to which it remains a good idea (and sometimes provably optimal) to have every parameter set on almost as often as off. We propose the first exact algorithm based on integer programming and a faster heuristic that often produces optimal solutions, both outperforming or competitive with their baselines.
This paper grew out of my undergraduate research on the structure of optimal covering arrays at Bucknell.