Let's start with set covering problems. More precisely, let's say we have a set of demand nodes I and a set of locations J. The i and j, they are two sets. For example, in the graph here, we use squares to denote locations, and then we use circles to denote demand. You may assume that there are four markets or they are four tongues and then there are three different places for you to make facilities. Also this is the idea of locations and demands. We know the distance. The distance, traveling time, traveling cost, whatever between demand i and the location j is d_ij, which is a positive number for each pair of i and j. This is something we already know. Maybe we know this is 10 km, this is 20 km and so on and so on. We also know that there is a service level S, which says demand i is covered by location j if and only if d_ij is less than S. What does that mean? Example is here. Let say you are building hospitals and then you say S is 50 km. What does that mean? You are saying that we hope that each tongue or each village may have access to a nearby hospital where the location, where the distance is within 50 km. When we locate one facility, where you say this facility covers that particular market, that particular demand if the distance is lower than this threshold. Our question is, how may we allocate as few facilities as possible to cover all demands? The example at the right-hand side is that, we are having this particular graph. Originally, all the i j pairs are there. For example, there is the link from here to there. There is also something which is called d_ij, in this case is d_41. We actually know that there's a distance d_41. There's also d_42, and so on. But the thing is that, we don't see a link here and there, because d_41 and d_42, they are greater than 50 km. In that case, no matter you build facility 1 or facility 2, you will still leave demand 4 uncovered. It is assumed that only facility 3 can cover demand 4, so we have a link here. Pretty much the graph you observe here is a graph after some simplification because we remove those links where d_ij is greater than S. But if that's the case, then very quickly you may see what's the optimal solution, you build one facility here and another facility here. With two facilities, you may cover everybody. If you build facilities as 1, 2, you fail, 1, 3, you fail, and building one single facility always you will fail. Building facilities at 2, 3 is an optimal solution. What we want is a model that may help us find an optimal solution. Let's try it. First, we don't really care about d_ij actually. As long as I cover you, it doesn't matter whether you are two kilometers from me or 20 kilometers from me. I'm going to convert d_i j to a_ij, d_ij less than S means covering. In that case, I would set a_ij to be one. Otherwise, a_ij I will set it to zero. On these parameter a_ij means, whether demand i can be covered by location j. If that's the case, I'm going to set a_ij to be one. Once I have this, then the remaining things would be simple. I'm going to define the decision variable called x_j. X_j is one if a facility is built at location j, otherwise it's zero. Then let's read this formulation. I want to minimize the total number of facilities I've built. So I want to minimize the sum of x_j for each demand i. I take a look at all those facilities. For each facility, I take a look at whether this facility covers me or not. Among all those facilities that covers me, at least one of them must be built. This is the set covering constraint. For each customer, among all those facilities that may cover this guy, one of them must be built. At least one of them. Finally, these are binary decisions. Because that's binary decisions, this is naturally an integer program, and these help us to determine the minimum facility way to cover everybody. Of course, there can be a weighted version where we don't minimize sum of x_j. We mean minimize the sum of w_j, x_j. In that case, w_j may be for example the cost of building that facility. We don't really care about the number of facilities. Instead that we care about the total cost we spend to build facilities. That's set covering problems. Use the most efficient way to cover everybody. Somehow sometimes we are talking about a different case. We talked about maximum covering. Now again we have a set of demands, set of locations. Again, we have distance, we have service levels, and we have the covering coefficient. These are all given. We are now restricted to build at most p facilities. P is a natural number 2,5,10. It's depending on the instance. The question is, we want to allocate at most p facilities to cover as many points as possible. So e.g. if we are only allowed to build one facility, we're going to build a Facility 2 because that's the best because that allows us to cover three points. If you build it at Facility 1 two points, Facility 3 two points. When p is one, building a facility at location two is optimal. But when p is two you are allowed to build two facilities. Building facilities at locations 1 and 3 is optimal. Two and 3 is also optimal. In that case, it doesn't really matter whether you build at 1,3 or 2,3 because you would cover the same number of demands, of which means four. Let's do the formulation. Still x_j would be one if a facility is built as location j and zero otherwise. But now we need a new set of decision variables. We need to have y_i to be one if demand i is covered or zero otherwise. With that, we are able to write down our objective function. We want to maximize the sum of y_i and the number of demand points that we may cover. Now how to do that? The first thing is that the number of facilities we build cannot be greater than p. That's okay. Binary. The heart of this formulation is actually here. Well, for each customer, that's take a look at whether this customer is covered by any nearby open facility. But this particular term is the same as that set covering terms and the left-hand side in the previous situation. In the previous case, is that sum of a_ij x_j for all j must be greater than or equal to one for or i. Instead covering, we impose this particular formulation, saying that for each customer, you need to cover this customer. But now we don't need to do that because now we try our best to cover a lot of customers. If you really cover it, you'll get one point. If your left-hand side is greater than or equal to one, may be 2,3,5 or 1, you are allowed to set your y_i to be one. If your left-hand side, unfortunately is zero, then you y_i must be zero. With all of these together, you are able to maximize the total number of demands you may cover. Again, we have this weighted version. You probably don't care about the number of towns you cover. Probably you care about the number of citizens you cover. Then w_i may be the number of citizens in town i, and then this becomes the weighted version.
