### A faster branch-and-bound algorithm for the test-cover problem based on set-covering techniquesA faster branch-and-bound algorithm for the test-cover problem based on set-covering techniques

Access Restriction
Subscribed

 Author Fahle, Torsten ♦ Tiemann, Karsten Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Branch-and-bound ♦ Lagrangian relaxation ♦ Set-cover problem ♦ Test-cover problem ♦ Variable fixing Abstract 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 by De Bontridder et al. [2002]. Based on their work, we introduce several improvements that are compatible with all techniques described in De Bontridder et al. [2002] and the more general setting of $\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2007-02-09 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 11

#### Open content in new tab

Source: ACM Digital Library