Difference between revisions of "Set covering problem"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Added a second application)
(Completed the applications section.)
Line 3: Line 3:
 
== 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>
+
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> The problem has many applications in the airline industry, and it was explored on an industrial scale as early as the 1970s.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span>
  
 
== Methodology ==
 
== Methodology ==
Line 33: Line 33:
 
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 location problem
 
;The optimal location problem
: This set covering problems is concerned with maximizing the coverage of some public facility placed at different locations.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> Consider the problem of placing fire stations to serve the towns of some city.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> 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.
+
: This set covering problems is concerned with maximizing the coverage of some public facility placed at different locations.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">3</span> Consider the problem of placing fire stations to serve the towns of some city.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">4</span> 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 optimal route selection problem
:Consider the problem of selecting the optimal bus routes to place pothole detectors. Due to scarcity of the physical sensors, the problem does not allow for placing a detector at every road. The task of finding the maximum coverage using a limited number of detectors could be formulated as a set covering problem.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">4</span> Specifically, giving a collection of routes '''''U''','' where each route itself is divided into segments. The segments of two routes can overlap. The goal is then to select the routes that maximize number of covered segments.
+
:Consider the problem of selecting the optimal bus routes to place pothole detectors. Due to scarcity of the physical sensors, the problem does not allow for placing a detector at every road. The task of finding the maximum coverage using a limited number of detectors could be formulated as a set covering problem.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">5</span> Specifically, giving a collection of routes '''''U''','' where each route itself is divided into segments. The segments of two routes can overlap. The goal is then to select the routes that maximize number of covered segments.
 
;The airline crew scheduling problem
 
;The airline crew scheduling problem
:
+
:An important application of large-scale set covering is the airline crew scheduling problem, which pertains to assigning airline staff to work shifts.<sup>2,6</sup> Thinking of the collection of flights as a universal set to be covered, we can formulate a set covering problem to search for the optimal assignment of employees to flights.
 
:
 
:
 
==Conclusion==
 
==Conclusion==
Line 44: 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
 +
#RUBIN, J. (1973). A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling. ''Transportation Science,'' ''7''(1), 34-48. Retrieved November 23, 2020, from <nowiki>http://www.jstor.org/stable/25767684</nowiki>
 
#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>
 
#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
 
#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
 
#Ali, J., & Dyo, V. (2017). Coverage and Mobile Sensor Placement for Vehicles on Predetermined Routes: A Greedy Heuristic Approach. ''Proceedings of the 14th International Joint Conference on E-Business and Telecommunications''. doi:10.5220/0006469800830088
 
#Ali, J., & Dyo, V. (2017). Coverage and Mobile Sensor Placement for Vehicles on Predetermined Routes: A Greedy Heuristic Approach. ''Proceedings of the 14th International Joint Conference on E-Business and Telecommunications''. doi:10.5220/0006469800830088
 +
#Marchiori, E., & Steenbeek, A. (2000). An Evolutionary Algorithm for Large Scale Set Covering Problems with Application to Airline Crew Scheduling. ''EvoWorkshops''.

Revision as of 15:34, 23 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 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.1 The problem has many applications in the airline industry, and it was explored on an industrial scale as early as the 1970s.2

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 must 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 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.3 Consider the problem of placing fire stations to serve the towns of some city.4 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
Consider the problem of selecting the optimal bus routes to place pothole detectors. Due to scarcity of the physical sensors, the problem does not allow for placing a detector at every road. The task of finding the maximum coverage using a limited number of detectors could be formulated as a set covering problem.5 Specifically, giving a collection of routes U, where each route itself is divided into segments. The segments of two routes can overlap. The goal is then to select the routes that maximize number of covered segments.
The airline crew scheduling problem
An important application of large-scale set covering is the airline crew scheduling problem, which pertains to assigning airline staff to work shifts.2,6 Thinking of the collection of flights as a universal set to be covered, we can formulate a set covering problem to search for the optimal assignment of employees to flights.

Conclusion

References

  1. 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
  2. RUBIN, J. (1973). A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling. Transportation Science, 7(1), 34-48. Retrieved November 23, 2020, from http://www.jstor.org/stable/25767684
  3. 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
  4. 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
  5. Ali, J., & Dyo, V. (2017). Coverage and Mobile Sensor Placement for Vehicles on Predetermined Routes: A Greedy Heuristic Approach. Proceedings of the 14th International Joint Conference on E-Business and Telecommunications. doi:10.5220/0006469800830088
  6. Marchiori, E., & Steenbeek, A. (2000). An Evolutionary Algorithm for Large Scale Set Covering Problems with Application to Airline Crew Scheduling. EvoWorkshops.