# Difference between revisions of "Set covering problem"

Khaledfahat (talk | contribs) m |
|||

Line 1: | Line 1: | ||

Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud | Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud | ||

− | |||

− | |||

== Introduction == | == Introduction == | ||

− | + | The set covering problem is a significant NP-hard problem in combinatorial optimization. In the set covering problem, two sets are given: a set '''''U''''' of elements and a set '''''S''''' of subsets of the set '''''U'''''. Each subset in '''''S''''' is associated with a predetermined cost, and the union of all the subsets covers the set '''''U'''''. This combinatorial problem then concerns finding the optimal number of subsets whose union covers the universal set while minimizing the total cost.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1</span> | |

− | |||

− | |||

== Methodology == | == Methodology == | ||

Line 36: | Line 32: | ||

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 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 | + | ;The optimal location problem |

− | : This set covering problems is concerned with maximizing the | + | : This set covering problems is concerned with maximizing the coverage of some public facility placed at different locations.2 Consider the problem of placing fire stations to serve the towns of some city.3 If each fire station can serve its town and all adjacent towns, we can formulate a set covering problem where each subset consists of a set of adjacent towns. The problem is then solved to minimize the required number of fire stations to serve the whole city. |

− | ;The | + | ;The optimal route selection problem |

: | : | ||

;The airline crew scheduling problem | ;The airline crew scheduling problem | ||

Line 48: | Line 44: | ||

==References== | ==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 | #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 | ||

+ | #Church, R., ReVelle, C. The maximal covering location problem. ''Papers of the Regional Science Association'' 32, 101–118 (1974). <nowiki>https://doi.org/10.1007/BF01942293</nowiki> | ||

+ | #Aktaş, E., Özaydın, Ö, Bozkaya, B., Ülengin, F., & Önsel, Ş. (2013). Optimizing Fire Station Locations for the Istanbul Metropolitan Municipality. ''Interfaces,'' ''43''(3), 240-255. doi:10.1287/inte.1120.0671 |

## Revision as of 10:05, 22 November 2020

Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud

## Introduction

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

*of subsets of the set*

**S***. Each subset in*

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

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

**U**## 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 with 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 location problem
- This set covering problems is concerned with maximizing the coverage of some public facility placed at different locations.2 Consider the problem of placing fire stations to serve the towns of some city.3 If each fire station can serve its town and all adjacent towns, we can formulate a set covering problem where each subset consists of a set of adjacent towns. The problem is then solved to minimize the required number of fire stations to serve the whole city.
- The optimal route selection 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 - Church, R., ReVelle, C. The maximal covering location problem.
*Papers of the Regional Science Association*32, 101–118 (1974). https://doi.org/10.1007/BF01942293 - Aktaş, E., Özaydın, Ö, Bozkaya, B., Ülengin, F., & Önsel, Ş. (2013). Optimizing Fire Station Locations for the Istanbul Metropolitan Municipality.
*Interfaces,**43*(3), 240-255. doi:10.1287/inte.1120.0671