Let's start with set covering problems. More precisely lets say we have a set of demand knowns, I and a set of locations J. 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 there are four towns, and then there are three different places for you to make facilities. This is the idea of locations and demands. We know the distance, traveling time, traveling costs, whatever between demand I in the location J is d_ij which is a positive number for each pair of i_lj. This is something we already know. Maybe we know this is 10 kilometers, this is 20 kilometers, 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? An example is here. Let's say you are building hospitals and then you say s is 50 kilometers, so what does that mean? You are saying that we hope that each town or each village may have access to a nearby hospital where the distance is within 50 kilometers. When we locate one facility, we 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 ij pairs are there. For example, there is a 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 is also d_42, and so on. But the thing is that we don't see a link here and there because d_41 and the d_42, they are greater than 50 kilograms. In that case, no matter you build facility 1 or facility 2, you will still leave demand 4 uncovered. It is assumed that only facilities 3 can cover demand 4. We have a link here. Pretty much with the graph you observe here is a graph after some simplification because we remove those links where d_ij is greater than s. 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 one, two, you fail. One, three, you fail. Building one single facility always you will fail. Building facilities at two, three is an optimal solution. What we want is the 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_ij 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. This parameter a_ij means, whether demand i can be covered by location i. 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 built. 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. And finally, these are binary decisions. Because that's binary decisions, this is naturally an integer program, and this helps 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 xj, we minimize the sum of wj, xj. In that case, wj may be, for example, the cost of building that facility. We don't really care about the number of facilities, instead, we care about the total cost we spend to build facilities. Also that set covering problems. Use the most efficient way to cover everybody. Somehow sometimes we are talking about a different case. We talk 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 demand points as possible. For example, if we are only allowed to build one facility, we're going to build facility two, because that's the best because that allows us to cover three points. If you build it at facility one, two-points, facility three, two-points. When p is one, building a facility at location two is optimal. What if p is two? When p is two, you are allowed to build two facilities. So building facilities at locations one and three is optimal, two and three is also optimal. In that case, it doesn't really matter whether you build at one-three or two-three because you would cover the same number of demands, which means four. Let's do the formulation. Still, xj would be one. If a facility is built at location j and zero otherwise. But now we need a new set of decision variables. We need to have yi 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 yi, or 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, binary. The heart of this formulation is actually here. Well, for each customer, let's take a look at whether this customer is covered by any nearby open facility. This particular term is the same as that set covering term at the left-hand side in the previous situation. In the previous case is that sum of a_ ijx_ j for all j must be greater than or equal to one for all 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 get one point. If your left hand side is greater than or equal to one, it may be 2,3,5 or 1. You are allowed to set your yi to be one. If your left-hand side, unfortunately is zero, then you are yi 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 wi may be the number of citizens in town i, then this becomes the weighted version.