Thumbnail
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

   Open content in new tab
Source: ACM Digital Library