# Difference between revisions of "Set covering problem"

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 = {${\displaystyle u_{i}}$, ….. ${\displaystyle u_{m}}$} as the universe of elements and S = {${\displaystyle s_{1}}$, ….,${\displaystyle s_{n}}$} as a collection of subsets such that ${\displaystyle s_{i}}$ ${\displaystyle \in }$U and the union of ${\displaystyle s_{i}}$ cover U (i.e. ${\displaystyle \cup }$${\displaystyle s_{i}}$ = U ). Addionally, each set ${\displaystyle s_{i}}$ must cover at least one element of U and has associated cost ${\displaystyle c}$ that is larger than zero (i.e. ${\displaystyle c_{i}}$ > 0). The objective is to find the minimum cost sub-collection of sets X ${\displaystyle \in }$ S that covers all the elements in the universe U.

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

Decision variables

${\displaystyle y_{i}={\begin{cases}1,&{\text{if subset }}i{\text{ is selected}}\\0,&{\text{otherwise }}\end{cases}}}$

Objective function

minimize ${\displaystyle \sum _{i=1}^{n}c_{i}y_{i}}$

Constraints

${\displaystyle \sum _{i=1}^{n}a_{ij}y_{i}>=1,\forall j=1,....,m}$

${\displaystyle y_{i}\in \{0,1\},\forall i=1,....,n}$

The objective function ${\displaystyle \sum _{i=1}^{n}c_{i}y_{i}}$ is defined to minimize the number of subset ${\displaystyle s_{i}}$ that cover all elements in the universe by minimizing its total cost. The first constraint implies that every element j in the universe U must be be covered where ${\displaystyle a_{ij}}$=1 if j ${\displaystyle \in }$ ${\displaystyle s_{i}}$ and 0 otherwise. The second constraint ${\displaystyle y_{i}\in \{0,1\}}$ indicates that the decision variables are binary.

## Numerical Example

Let’s consider a simple example where we assign cameras at different locations. Each location covers some areas of stadiums, and our goal is to put the least amount of cameras such that all areas of stadiums are covered. We have stadium areas from 1 to 15, and possible camera locations from 1 to 8.

We are given that camera location 1 covers stadium areas {1,3,4,6,7}, camera location 2 covers stadium areas {4,7,8,12}, while the remaining camera locations and the stadium areas that the cameras can cover are given in table 1 below:

Table 1
1 1,3,4,6,7
2 4,7,8,12
3 2,5,9,11,13
4 1,2,14,15
5 3,6,10,12,14
6 8,14,15
7 1,2,6,11
8 1,2,4,6,8,12

To reformulate the problem, we can list the stadium areas and the camera locations that cover each stadium area. For instance, stadium area 1 can be covered with camera location {1,4,7,8}, stadium area 2 can be covered with camera location {3,4,7,8}, while the rest are given in table 2 below:

Table 2
1 1,4,7,8
2 3,4,7,8
3 1,5
4 1,2,8
5 3
6 1,5,7,8
7 1,2
8 2,6,8
9 3
10 5
11 3,7
12 2,5,8
13 3
14 4,5,6
15 4,6

We can then represent the above information using binary values. If the stadium area ${\displaystyle i}$ can be covered with camera location ${\displaystyle j}$, then we have ${\displaystyle y_{ij}=1}$. If not,${\displaystyle y_{ij}=0}$. For instance, stadium area 1 is covered by camera location 1, so ${\displaystyle y_{11}=1}$, while stadium area 1 is not covered by camera location 2, so ${\displaystyle y_{12}=0}$. The binary variables ${\displaystyle y_{ij}}$ values are given in the table below:

Table 3
1 2 3 4 5 6 7 8
1 1 1 1 1
2 1 1 1 1
3 1 1
4 1 1 1
5 1
6 1 1 1 1
7 1 1
8 1 1 1
9 1
10 1
11 1 1
12 1 1 1
13 1
14 1 1 1
15 1 1

We introduce another binary variable ${\displaystyle z_{j}}$ to indicate if a camera is installed at location ${\displaystyle j}$. ${\displaystyle z_{j}=1}$ if camera is installed at location ${\displaystyle j}$, while ${\displaystyle z_{j}=0}$ if not.

Our objective is to minimize ${\displaystyle \sum _{j=1}^{8}z_{j}}$. For each stadium, there’s a constraint that the stadium area ${\displaystyle i}$ has to be covered by at least one camera location. For instance, for stadium area 1, we have ${\displaystyle z_{1}+z_{4}+z_{7}+z_{8}\geq 1}$z1 + z4 + z7 + z8 >= 1, while for stadium 2, we have z3 + z4 + z7 + s8 >= 1. All the 15 constraints that corresponds to 15 stadium areas are listed below:

1. Z1+z4+z7+z8 >= 1
2. Z3+z4+z7+z8 >= 1
3. Z1+z5 >= 1
4. Z1+z2+z8 >= 1
5. Z3 > =1
6. Z1+z5+z7+z8 >= 1
7. Z1+z2 >= 1
8. Z2+z6+z8 >= 1
9. Z3 >= 1
10. Z5 >=1
11. Z3+z7 >= 1
12. Z2+z5+z8 >= 1
13. Z3 >= 1
14. Z4+z5+z6 >=1
15. Z4+z6 >=1

From constraint 5,9,13, we can obtain Z3 = 1. Thus we no longer need constraint 2 and 11 as they are satisfied when z3 = 1. With Z3 = 1, the constraints left are:

1.Z1+z4+z7+z8 >= 1

3.Z1+z5 >= 1

4.Z1+z2+z8 >= 1

6.Z1+z5+z7+z8 >= 1

7.Z1+z2 >= 1

8.Z2+z6+z8 >= 1

10.Z5 >=1

12.Z2+z5+z8 >= 1

14.Z4+z5+z6 >=1

15.Z4+z6 >=1

Now if we take a look at constraint 10, Z5 >=1 so Z5 shall equal to 1. As z5 = 1, constraint 3,6,12,14 are satisfied no matter what other z values are taken.

The remaining constraints are:

 1.Z1+z4+z7+z8 >= 1 4.Z1+z2+z8 >= 1 7.Z1+z2 >= 1 8.Z2+z6+z8 >= 1 15.Z4+z6 >=1

If constraint 7 is satisfied, z1 + z2 >= 1, then constraint 4 will be satisfied as z8 >= 0.

The remaining constraints that we need to consider are:

 1.Z1+z4+z7+z8 >= 1 7.Z1+z2 >= 1 8.Z2+z6+z8 >= 1 15.Z4+z6 >=1

The next step is to focus on constraint 7 and 15. We can have at least 4 combinations of z1,z2,z4,z6 values.

A:  z1 = 1, z2 = 0, z4 = 1, z6 = 0

B:  z1 = 1, z2 = 0, z4 = 0, z6 = 1

C:  z1 = 0, z2 = 1, z4 = 1, z6 = 0

D:  z1 = 0, z2 = 1, z4 = 0, z6 = 1

We can then discuss each combination and determine z7, z8 values for constraint 1 and 8 to be satisfied.

For combination A: constraint 1 already satisfied, we need z8 = 1 to satisfy constraint 8.

For combination D: we need z7 or z8 = 1 to satisfy constraint 1, while constraint 8 already satisfied.

Our final step is to compare the four combinations. Since our objective is to minimize the sum of zj from j = 1 to j = 8, since combinations B and C requires the least amount of zs to be 1, they are the optimal solutions.

To conclude, our two solutions are:

Z3 = 1, Z5 = 1, Z1 = 1, and Z6 = 1

Z3 = 1, Z5 = 1, Z2 = 1, and Z4 = 1

The minimum number of cameras that we need to install is 4.

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

The set covering problem, which aims to find the least number of subsets that cover some universal set, is a widely known NP-hard combinatorial problem. Due to its applicability to route planning and airline crew scheduling, several methods have been proposed to solve it. Its straightforward formulation allows for the use of off-the-shelf optimizers to solve it. Moreover, heuristic techniques and greedy algorithms can be used to solve large-scale set covering problems for industrial applications.

## 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.