# Difference between revisions of "Set covering problem"

(Added some main applications) |
Khaledfahat (talk | contribs) |
||

Line 10: | Line 10: | ||

== Methodology == | == 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<sub>1</sub>, ….. u<sub>m</sub>} and S = {s<sub>1</sub>, ….s<sub>n</sub>} as a collection of subsets such that s<sub>i</sub> C U and their union cover U. Addionally, each set si should cover at least one element of U and has associated cost c that is larger than zero, cj > 0. The objective is to find the minimum cost subcollection of sets X C S that covers all the elements in U. | ||

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

+ | '''Decision variables''' | ||

+ | x = begin{cases}1 & if subset i is selected | ||

+ | 0 & otherwiseend{cases} | ||

+ | i | ||

+ | |||

+ | |||

+ | '''Objective function''' | ||

+ | |||

+ | |||

+ | '''Constraints ''' | ||

== Example == | == Example == |

## Revision as of 02:17, 22 November 2020

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} C U and their union cover U. Addionally, each set si should cover at least one element of U and has associated cost c that is larger than zero, cj > 0. The objective is to find the minimum cost subcollection of sets X C S that covers all the elements in U.

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

**Decision variables**

x = begin{cases}1 & if subset i is selected

0 & otherwiseend{cases}

i

**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