A Branch-and-Price-and-Cut algorithm for non-adaptive two-dimensional group testing with equal group size
Tifaout Almeftah  1@  , Diego Cattaruzza  1, 2, 3@  , Martine Labbé  1, 4@  , Frederic Semet  1, 2, 5@  
1 : Inria Lille - Nord Europe
Institut National de Recherche en Informatique et en Automatique
2 : Ecole Centrale de Lille
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France
3 : Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Université de Lille : UMR9189, Centrale Lille : UMR9189, Centre National de la Recherche Scientifique : UMR9189
4 : Université Libre de Bruxelles [Bruxelles]
5 : Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189  (CRIStAL)
Ecole Centrale de Lille, Institut National de Recherche en Informatique et en Automatique, Institut Mines-Télécom [Paris], Université de Lille, Centre National de la Recherche Scientifique : UMR9189
Bâtiment M3, Université Lille 1, 59655 Villeneuve dÁscq Cedex FRANCE -  France

Group testing involves screening a large scale population with low prevalence to have a binary characteristic (e.g. presence of disease, product defect, system error...) in groups. If a test on a group is negative, the entire group is classified as negative. Otherwise, at least one individual is positive, and the positive group is tested again either individually or in smaller groups. We study a non-adaptive two-dimensional design with equal size groups where each individual belongs to two different groups under imperfect tests and heterogeneous risk profiles. We consider a convex combination of misclassification error and expected number of tests based objective. We have proposes a quadratic set covering model with an exponential number of variables. To solve to studied problem, we have proposed a Branch-and-Price-and-Cut algorithm where the linear relaxation is solved with column-dependent-row generation and strengthened with clique and odd-hole separation procedures. The proposed approaches are under validation on randomly generated instances with up to 36 individuals.


Personnes connectées : 23 Vie privée
Chargement...