Welcome back to operations research. We're still at this part algorithms. Today, we will talk about something new about algorithms. You may ask, well, we have learned linear programming, integer programming, non-linear programming. What else may we do? First, we may apply these ideas to a real case. Today, I'm going to give you a case study. We're going to see how in practice we may solve a problem that may be solved with operations research. In today's case study, we will talk about a facility location problem. Well, this is not new to you. For many cases, we need to decide the locations or to decide the numbers of our facilities. You may want to build distribution centers. You may want to build retail stores. You may want to build new bike stations. All kinds of possibilities exist when you want to provide some services. The story is the following. There's a company in Taiwan, then this company is doing some IT service. One day there comes a new CEO. The CEO looks at the current setting around the whole Taiwan. There are a few service facilities, so they allocate engineers in that facility, maybe one in Taipei, maybe one in Tainan, maybe one in Gaozhong, and so on. In each of these are service facilities, there is a region that the customers inside the region is allocated to this facility so that if a customer's IT service system it has some breakdowns, we may send people to the customer as soon as possible. There are some customer points around the whole Taiwan, something like this. Each customer is assigned a facility to do the service, something like this. The thing is that we are having several number of facilities. In that particular case, they have 12 facilities when the CEO goes onto the stage. Around the 12th facilities, the CEO takes a look at the financial reports, takes a look at the cost, takes a look at a number of services each facility takes. There may be a question asking about, do we really need these 12 facilities? Maybe we need more, maybe we need fewer. The question is that, well, this facility looks useless, what is going to happen, if we remove this facility? If we remove one facility, we're going to save some operating costs at that facility. We don't need to pay for the rent, we don't need to pay for the management fee, and so on and so on. That's good. But once you cancel, once you remove one facility, these customers need to be reassigned. Maybe you reassign this to the new facility, this one to the new facility, this one to the new facility here. This may be something you need to do. You need to reassign customers. But the thing is that well, first, for this existing facility, if you assign new customers to this facility, you need to make sure that the engineers there are enough to deal with the new demands. That's one thing. You may have some capacity issues. Second, this path looks very long, you need to send your engineers back and forth to travel a long distance. If you drive, that takes time, that takes Oyo, Oyo takes money. That may increase your traveling costs or service cost. When you want to make a decision like whether you want to cut down this facility, there are too many things to consider. Not to mention that in this particular real case, the number of customers is around fifteen thousands. In that case, you really need to make a lot of decisions. Let's assumed X_ij is a decision variable, which is zero or one. X_ij is one. If you use facility j to serve customer i, then you may do a simple calculation to see how many binary variables you have in this particular problem. In this large-scale problem, maybe it is not possible or maybe it is not a good idea to use solvers, to use branch and bound or whatever algorithm to really find an optimal solution. In this case, we want to give you a very important idea, which is called heuristic algorithms. In a heuristic algorithm, what we want to do is not to find an optimal solution. Instead, what we want is to find a near optimal solution. We want to use a short time to do a very efficient search to get a solution that is feasible and close to optimal. You may ask several questions. First, how may we design these algorithms we will show you? Second, how may we show whether a solution is close to optimal or not? We will show you. Eventually, we will also give you some discussions about when you want to implement in operations research solution to practice. What are some management or people's things that you need to work with. That will be today's lecture. Later let's start.
