Solution techniques for the Large Set Covering Problem

Given a finite set EE and a family F={E1,…,Em}F={E1,…,Em} of subsets of EE such that FF covers EE, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of FF that also covers EE. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that EE and the subsets EiEi are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of FF that does not cover EE. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the kk-colouring problem which is formulated as a constraint satisfaction problem.