# Set covering problem

Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud

The set covering problem is a significant NP-hard problem in combinatorial optimization. In the set covering problem, two sets are given: a set * S* of elements and a set

*of subsets of the set*

**A***. Each subset in*

**S***is associated with a predetermined cost, and the union of all the subsets covers the set*

**A***. This combinatorial problem then concerns finding the optimal number of subsets whose union covers the universal set while minimizing the total cost.1*

**S**## Introduction

## Methodology

The mathematical formulation of the set covering problem is define as follows. We define U as the universe of elements such that U = {u_{1}, ….. u_{m}} and S = {s_{1}, ….s_{n}} as a collection of subsets

such that s_{i} U and their union cover U (i.e. s_{i} = U ). Addionally, each set s_{i} must cover at least one element of U and has associated cost c that is larger than zero (i.e. c_{i} > 0). The objective

is to find the minimum subcollection of sets X S that covers all the elements in U and has the minimum cost.

An integer linear program (ILP) model can be formulated for the set covering problem as follows:

**Decision variables**

**Objective function**

**Constraints **

## Example

## Applications

The applications of the set covering problem span a wide range of applications, but its usefulness is evident in industrial and governmental planning. Variations of the set covering problem that are of practical significance include the following.

- The optimal covering location problem
- This set covering problems is concerned with maximizing the population coverage of some public facility.2 Consider the problem of placing hospitals at different cities around some state.
- The cell tower coverage problem
- The airline crew scheduling problem

## Conclusion

## References

- Grossman, T., & Wool, A. (1997). Computational experience with approximation algorithms for the set covering problem.
*European Journal of Operational Research,**101*(1), 81-92. doi:10.1016/s0377-2217(96)00161-0