Set covering problem: Difference between revisions
Khaledfahat (talk | contribs) |
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> | 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> <math>\in</math>U and their union cover U (i.e. <math>\cup</math>s<sub>i</sub> = U ). Addionally, each set s<sub>i</sub> should cover at least one element of U and has associated cost c that is larger than zero (i.e. c<sub>i</sub> > 0). The objective | |||
is to find the minimum subcollection of sets X <math>\in</math> 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: | An integer linear program (ILP) model can be formulated for the set covering problem as follows: | ||
'''Decision variables''' | '''Decision variables''' | ||
0 & | <math>x_i = \begin{cases} 1, & \text{if subset }i\text{ is selected} \\ 0, & \text{otherwise } \end{cases}</math> | ||
| Line 25: | Line 28: | ||
'''Constraints ''' | '''Constraints ''' | ||
==Example== | |||
== Applications == | ==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 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 | ;The optimal covering location problem | ||
:This set covering problems is concerned with maximizing the population coverage of some public facility.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> Consider the problem of placing hospitals at different cities around some state. | : This set covering problems is concerned with maximizing the population coverage of some public facility.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> Consider the problem of placing hospitals at different cities around some state. | ||
;The cell tower coverage problem | ;The cell tower coverage problem | ||
: | : | ||
| Line 39: | Line 42: | ||
: | : | ||
: | : | ||
== Conclusion == | ==Conclusion== | ||
== 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 | ||
Revision as of 01:39, 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 A of subsets of the set S. Each subset in A 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
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 = {u1, ….. um} and S = {s1, ….sn} as a collection of subsets
such that si U and their union cover U (i.e. si = U ). Addionally, each set si should cover at least one element of U and has associated cost c that is larger than zero (i.e. ci > 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