The Multi-Mode Set Covering Problem

Several applications in the fields of computational biology, surveillance systems and facility location among others can be formalized as a generalization of the set covering problem. In this talk, we present the multi-mode set covering problem. Given a set of modalities M, a ground set S, |M| families of subsets of S, one for each modality, and a cost function defined on all the subsets of S, the multi-mode covering problem (MMCP) requires finding a least total cost collection of subsets such that each element of the ground set is covered in all the modes, with the additional condition that some constraints (of knapsack type) on the selected sets are satisfied. The MMCP is clearly NP complete and is difficult to solve by commercial solvers. We present a branch-and-bound algorithm based on lagrangian relaxation. To compute feasible solutions of the problem, we implement a Variable Neighbourhood Search metaheuristic. The algorithms are tested on a set of randomly-generated benchmark instances