To illustrate this model, consider the following location problem: A city is reviewing the location of its fire stations. The city is made up of a number of neighborhoods, as illustrated in Figure 1.
Figure 1: Map of the city
A fire station can be placed in any neighborhood. It is able to handle the fires for both its neighborhood and any adjacent neighborhood (any neighborhood with a non-zero border with its home neighborhood). The objective is to minimize the number of fire stations used.
We can create one variable for each neighborhood j. This variable will be 1 if we place a station in the neighborhood, and will be 0 otherwise. This leads to the following formulation
The first constraint states that there must be a station either in neighborhood 1 or in some adjacent neighborhood. The next constraint is for neighborhood 2 and so on. Notice that the constraint coefficient is 1 if neighborhood i is adjacent to neighborhood j or if i=j and 0 otherwise. The jth column of the constraint matrix represents the set of neighborhoods that can be served by a fire station in neighborhood j. We are asked to find a set of such subsets j that covers the set of all neighborhoods in the sense that every neighborhood appears in the service subset associated with at least one fire station.
One optimal solution to this is and the rest equal to 0.
This is an example of the set covering problem. The set covering problem is characterized by having binary variables, constraints each with a right hand side of 1, and having simply sums of variables as constraints. In general, the objective function can have any coefficients, though here it is of a particularly simple form.