Our last example about facility location is the fixed charge location problems. Here there is no limit on whether you need to cover everybody, there is no limit on the number of facilities you may build, is all about demand, supply, costs, and benefits. Again, there is a set of demand i, there is a set of location j. At a demand i, there is something called demand size, which is h_i. Later, you will see this somehow translate to the amount of service you need to spend on demand i, the unit shipping cost from location j to demand i is d_ij. You may consider these as shipping costs, moving costs, traveling cost, whatever. Somehow it measures the cost for j to serve i, and then there is a fixed construction costs at location j, which is f_j. Building facilities is not free, you need to pay some money. The question is how may we allocate some facilities to minimize the total shipping and the construction cost. What does that mean? Now we need to make two sets of decisions. First, we need to allocate facilities, and then among those open facilities, we need to assign them to customers. All the customers needs to be somehow served. You may serve a customer from a very far away facility, but then you need to pay a lot of cost. Lets take a look at this example. You have four demand points, you have three facility candidates. There are some options for you. For example, maybe you only open one facility. When you open one facility at facility two, you're going to see that, I'm going to serve 1, 2, 3, and 4 all by Facility 2, the cost somewhat seems to be moderate. If I only open one facility, probably I don't want to open Facility 3, because then I need to travel all the way to Facilities 1 and 2 and to Demand 1 and 2. That may be too much efforts. Maybe you want to open more than one facility, for example, Facility 2 and Facilities 3, maybe from facility three, serving customers 3 and 4 are easier because maybe it's cheaper, maybe it's closer. Then you'll use two facilities to serve two or four customers. The overall total shipping costs must be shorter because you are going to assign closer facilities to customers, but the overall facility construction costs would be higher. There's the trade off. Either you have higher shipping cost by building fewer facilities, or you have higher construction costs by building a lot of facilities. Now we still need x_j, x_j is one if a facility is built at location j, just like before. Then now we need something that is new. We need y_ij, y_ij would be one if the mean i is served by facility at location j. As I mentioned, we need to do that assignment thing, for each customer, we need to tell this customer who will be in charge of your service. That's why we need these y_ij thing. Let's take a look at this formulation. First, everything must be binary, that's fine. For each customer, the assignment thing must be completed. For each customer, there must be at least one facility serving these customer. Actually here because we are writing equality, this means exactly one facility should be in charge of that customer. We may also see that the opening decision and the assignment decision is, of course, connected. For each i_j pair, you are allowed to ask facility j to serve customer i only if you open that facility. If your x_j is zero, there is no way for you to set any y_ij to be one, because if you're facilities not open, it cannot serve anybody. Collectively, now we are able to formulate our objective function. We are trying to minimize the sum of the first thing. This part is the fixed construction cost. You construct, if you build more, you pay more. Here, the second part is your shipping cost. The case is that h_i is the number of times you need to travel to customer i, or maybe it's because they order a lot. Maybe it's because they are a lot of people, whatever. If you say facility j, needs to serve customer i, then we need to count the number of times you need to do the service and the per-service cost. You connect all of them, and then this is your fixed charge location problem. It is called the fixed charge problem because building a facility having a fixed cost. The previous model is an uncapacitated version because of a facility can serve any amount of demand. Sometimes you'll have a capacitated version, that means each facility has a limited capacity, that's called the k_j. In that case, a typical formulation is here. This means among all the facilities does take look at facility j. For facility j, there is capacity, and for all those customers that are assigned to facility j, I calculate, I sum up all the services I need to do. That total amount cannot be greater than the best I can do, the maximum I can do. The left-hand side is some kind of total demand assigned to me, the right-hand side is the maximum I can do. This is the capacitated version, which is typically called the capacitated the facility location problem called the CFL. The uncapacitated one we listed in the previous page is called UFL, uncapacitated facility location problem. Some remarks. When do you want to do set covering? Typically, that's the case when you build some public facilities, fire stations, police stations, so you need to take care of everyone, all the persons leaving in your region. Sometimes you want to do maximum covering. Typically that's when your budget is limited and when you are doing some business profit maximization, retail stores, cellular data networks. When do you do fixed charge locations? Typically that happens when the service cost is paid by you, and that depends on distances. Typically that's for example, distribution centers, fire stations may be another example. All these are examples of integer programming formulations and then they have different applications. Hopefully from this Introduction, you not only get some ideas about what may integer programming do, you also see how some facility location problems may appear around us, and the may be facilitated by integer programming.
