An Improved Branch-and-Bound Algorithm for the Test Cover Problem

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. At ESA'02 a collection of branch-and-bound algorithms was proposed by [BON02]. Based on their work, we introduce several improvements that are compatible with all techniques described in [BON02]. We present a faster data structure, cost based variable fixing and adapt an upper bound heuristic. 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.