A Faster Branch-and-Bound Algorithm for the Test Cover Problem Based on Set Covering Techniques

Torsten Fahle, Karsten Tiemann

Department of Computer Science, University of Paderborn

The test cover problem asks for the minimal number of tests needed to uniquely identify a disease, infection, etc. A collection of branch-and-bound algorithms was proposed in [BLLOS02]. Based on their work, we introduce several improvements that are compatible with all techniques described in [BLLOS02] and the more general setting of weighted test cover problems. We present a faster data structure, cost based variable fixing and adapt well-known set covering techniques including Lagrangian relaxation and upper bound heuristics. The resulting algorithm solves benchmark instances up to 10 times faster than the former approach and up to 100 times faster than a general MIP-solver.