Solution techniques for the Large Set Covering Problem Original Research Article

Given a finite set image and a family image of subsets of image such that image covers image, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of image that also covers image. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that image and the subsets image 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 image that does not cover image. 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 image-colouring problem which is formulated as a constraint satisfaction problem.