That was nice. We have a real problem. We showed you about conceptual modeling, mathematical modeling, and with that, we are able to do computer modeling. With a real computer program, we are able to run the program, get a solution, and you'll see that saves us seven million dollars per year. That seems to be a huge number. All of these are good. But going back to operations research, technically, we know that mathematical model is good, but maybe is not enough. That's why sometimes we need heuristic algorithms. The last thing I want to do in today's lecture is to show you a heuristic algorithm and some related discussions. A mixed integer program is good, but maybe it's not enough, especially if you expect to evaluate more candidate locations, maybe 40, maybe 50; if you expect to have more customers, maybe 220,000, maybe 30,000; if you expect to evaluate more decisions, maybe you have different types of customers, maybe you have different types of services, and so on. It's always possible for you to need a heuristic algorithm so that you may find a near optimal solution in a short time. It's always variable. Here we're going to, just as an example, show you one heuristic algorithm that makes sense. I need to tell you that the true heuristic algorithm that we developed and delivered to the company is more complicated than the one that I'm going to show you. But this one is good enough for us to illustrate the idea for teaching purpose. The heuristic algorithm here we want to demonstrate is a naïve greedy algorithm. Greedy here means we just look at several options. We are not looking at all the options, we'll look at some options and pick the one that is the best. With that, we then move further to consider another set of good solutions, and then we choose the best one, and so on and so on and so on. How do we do that? We start with a naïve solution, the current solution. We first try to open all facilities at the largest possible scale level. It's possible that there are too many facilities at two large levels. We don't need that many large facilities. Then we run several iterations. In each iteration, we greedily try to improve the current solution by choosing one facility to do one level of downsizing. For example, suppose we have five facilities, and therefore each facility we have three scales to choose from. Here, when we are talking about scale 0, that means we don't want to build that facility. Initially, we choose all the facilities at the largest level, then in each iteration we ask ourselves, well, is it good to downsize this first one? Or how about to downsize the second one, and so on and so on and so on? We have five downsizing options, and we pick the one that seems to be the best. Out of the five options, we choose the one that is the best. That does not mean in optimal solution, we should downsize that facility because we are not considering all the options in this iteration. But anyway, it's quite possible that if there's one downsizing option, that is good at this moment, then it's also good in the whole picture. We hope a local optimum is also a global optimum, even though it may not be always true. Let's say we choose this one, and then we will be staying with this solution, then we will keep going and ask ourselves, well, how about these five downsizing options? We always have five downsizing options, and among the five downsizing options, we will pick one. For example, maybe this one. Then we will ask again, first, second, third, fourth, and fifth, we still have five downsizing options, which one is optimal? We always ask this question, and then choose the one facility to downsize one level. Now here comes a question. If there are multiple facilities who's downsizing may reduce the total cost, then we want to choose the one with the largest reduction in cost. Then there must be a way for us to do the evaluation. That means once we choose to downsize one facility, we need to have a way to evaluate how to do the customer assignment, how to do engineering location, and then we need to estimate the total cost. We also need to do one thing, is that we know we will keep iterating, and there must be a place for us to stop. When to stop. If among all these possible downsizing thing. If no further downsizing is feasible and the cost are reducing, then we stop. First, we understand one thing, if you keep downsizing, then eventually your facilities will be not enough to host engineers. Then you don't have capacity to serve all the customers. If you keep downsizing, eventually your solutions will be infeasible, then you'll need to stop. Or if you keep downsizing, then at some time maybe you still have feasible solution, but then you'll need to serve customers from a too far location, and that costs a lot. If that's the case, then that's also not optimal. You keep doing iterations until you cannot find a better solution through downsizing, then you stop. We are almost done with the description of this algorithm. The only thing remains is how to evaluate how good a construction plan is. Now, given a construction plan with scale level for each facility, we now need to have a way to evaluate its feasibility and the cost. This question is also difficult because you have so many customers to assign and the assignment also has some impact on engineer allocation. Engineer allocation is not easy because that also has something to do with utility cost. We need to have a way to do that. As the heuristic algorithm here, we also use a heuristic way to do the evaluation. Again, that's a greedy method. We first list all the customers one by one, then for each customer, if we take a look at the customer and try to see whether there's any open facility that is close enough. If we cannot find one, we know for sure that this current construction plan is infeasible. Then we don't do further calculations, and then we return back to the main process saying that hey, don't do this downsizing. This downsizing is not good. If all the customers, at least there has won facilities to go, that is feasible, that is close enough. Then for each customer, we assign it to the closest open facility that has enough capacity. Understanding? Suppose I have a customer i and there a lot of facilities around it. Some facilities are near, some facilities are far. But you may also notice that a near facility may not be always open. We will take a look at i, and take a look at all those surrounding facilities to see which is an open facility that is the closest, maybe this one. Then we do the assignment. But when we want to do that assignment, we also understand that there is a capacity issue. There are two things that we may need to do. First, if there are already some engineers there, then adding one customer there may not be an issue. If that's the case, do it. If we say that one more engineer is needed for that facility and if the facility still have space to do that, then let's do it, assign a customer and add one more engineer. If unfortunately, that facility is already full because you already fixed the scale of that facility. If you cannot add more engineers, then you cannot assign the customer there, then you stop and try to do the next option. If you keep doing this, and then eventually you see there's no open facility that still have enough capacities to do the assignment, then you'll also conclude infeasibility, and then you return infeasibility to the original main process. Pretty much that's how we do the evaluation and if we combine the main downsizing decision and the greedy evaluation process, then we're pretty much done with this heuristic algorithm.
