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

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 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.

REFERENCES

• 1: Erling D. Andersen , Knud D. Andersen, Presolving in linear programming, Mathematical Programming: Series A and B, v.71 n.2, p.221-245, Dec. 20, 1995 [doi>10.1007/BF01586000]
• 2: Beasley, J. E. 1990. A lagrangian heuristic for set-covering problems. Naval Research Logistics 37, 151--164.
• 3: Berman, P., DasGupta, B., and Kao, M.-Y. 2004. Tight approximability results for test set problems in bioinformatics. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT '04). Lecture Notes in Computer Science, vol. 3111. Springer, New York. 39--50.
• 4: Caprara, A., Fischetti, M., and Toth, P. 2001. Algorithms for the set-covering problem. Annals of Operations Research 98, 353--371.
• 5: Chang, H. Y., Manning, E., and Metze, G. 1970. Fault Diagnosis of Digital Systems. Wiley, New York.
• 6: Koen M. J. De Bontridder , B. J. Lageweg , Jan K. Lenstra , James B. Orlin , Leen Stougie, Branch-and-Bound Algorithms for the Test Cover Problem, Proceedings of the 10th Annual European Symposium on Algorithms, p.223-233, September 17-21, 2002
• 7: De Bontridder, K. M. J., Halldórsson, B. V., Halldórsson, M. M., Hurkens, C. A. J., Lenstra, J. K., Ravi, R., and Stougie, L. 2003. Approximation algorithms for the test-cover problem. Mathematical Programming 98, 477--491.
• 8: Fischer, M. L. 1981. The lagrangian relaxation method for solving integer programming problems. Management Science 27, 1, 1--18.
• 9: Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. Freeman, San Francisco, CA.
• 10: Bjarni V. Halldórsson , Magnús M. Halldórsson , R. Ravi, On the Approximability of the Minimum Test Collection Problem, Proceedings of the 9th Annual European Symposium on Algorithms, p.158-169, August 28-31, 2001
• 11: Halldórsson, B. V., Minden, J. S., and Ravi, R. 2001b. PIER: Protein identification by epitope recognition. Currents in Computational Molecular Biology 2001, 109--110.
• 12: Held, M. and Karp, R. M. 1971. The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming 1, 6--25.
• 13: Johnson, D. S. 1974. Approximation algorithms for combinatorial problems. Journal of Computer and Systems Sciences 9, 256--278.
• 14: Lageweg, B. J., Lenstra, J. K., and Rinnooy Kan, A. H. G. 1980. Uit de practijk van de besliskunde. In Tamelijk briljant; Opstellen aangeboden aan Dr. T. J. Wansbeek. Amsterdam.
• 15: Claude Lemarechal, Lagrangian Relaxation, Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], p.112-156, May 15-19, 2000
• 16: Moret, B. and Shapiro, H. 1985. On minimizing a set of tests. SIAM Journal on Scientific and Statistical Computing 6, 983--1003.
• 17: Payne, R. W. 1981. Selection criteria for the construction of efficient diagnostic keys. Journal of Statistical Planning and Information 5, 27--36.
• 18: Rescigno, A. and Maccacaro, G. A. 1961. The information content of biological classification. In Information Theory: Fourth London Symposium. Butterworths, London. 437--445.
• 19: Rypka, E. W., Clapper, W. E., Brown, I. G., and Babb, R. 1967. A model for the identification of bacteria. Journal of General Microbiology 46, 407--424.
• 20: Rypka, E. W., Volkman, L., and Kinter, E. 1978. Construction and use of an optimized identification scheme. Laboratory Magazine 9, 32--41.
• 21: Tiemann, K. 2002. Ein erweiterter Branch-and-Bound-Algorithmus für das Test-Cover Problem. B.S. thesis, University of Paderborn.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Branch-and-bound, Lagrangian relaxation, set-cover problem, test-cover problem, variable fixing