Hi everyone, welcome back to operations research. So, this is Ling-Chieh Kung and we are still talking about models and applications. In this particular lecture we will introduce integer programming. So pretty much my plan for today is that I'm going to first give a brief introduction about integer programming or somehow. Let's just some kind of opening and then I will talk about how integer programming may help us to more interesting more powerful formulation, okay? It's not just setting those production quantities or a number of persons you hire to be in them else, which are very, very important. And then we will talk about three specific subjects facility location, machine schedule. And the vehicle routing. Pretty much these are examples showing you how to use integer programming modeling to help you solve some real problems. And at the same time, these three categories are also very fundamental, very useful when you are dealing with all kinds of operations management or related problems, okay? So I hope this plan makes sense to you. And later that's to it. So we have worked with linear programs, pretty much all those constraints, all those objective functions are linear and the variables are fractional. In some cases, variables actually should take integer values. If that's the case, then we're going to do Integer Programming. So a linear programming and integer programming they are different only at the type of variables. And typically when we say integer program, we are talking about linear integer program. Of course, it's still possible to have nonlinear integer program, but pretty much it's too difficult. It's not so useful. So, even though with non linearity, we may model and formulate more kinds of problems, but nonlinear integer programs turns out to be difficult to be solved. We don't know how to find an optimal solution. And if you have a model where we don't have an optimal solution, we don't know how to solve it. Then that model somehow becomes useless. So we will focus more on linear in teacher program. And this is the thing that has more applications in practice. So we're talking about applications. Let's take a look at some. So we know a number of steps in the many other cases, many other things may be planned with linear programming. That makes sense, okay? So we may use linear programs to help us understand how many people we should hire, and maybe how to assign them to where it works. The same problem is faced by Taco Bell. So Taco Bell is a restaurant champ in the United States. So when the story is made, when the application is implemented it has more than 6500 restaurants in the United States. And basically, the workers, there are a lot of workers a lot of steps with different kinds of skills, different kinds of positions. They need to be assigned to restaurants in shifts, okay? So this scheduling problem, and Taco Bell developed an integer program and teacher program to do this workforce scheduling problem. The thing is that how come previously United Airlines they use linear program, but the Taco Bell need to use integer program. There are many, many reasons, but one reason is that the number of steps in a restaurant is typically small. Typically, at any single moment in a restaurant or in fast food restaurant, you don't really have a lot of steps there. Maybe as the front, you only have two, or three, or five. Maybe you only have two, or three, or five in the kitchen and a few managers. So when you are scheduling thousands of workers, it doesn't really matter to run it down or running it up. So fractional values does not create a problem to you. But if you only need two or three or five persons, then that 4.3 or 3.7 really create some problems to you. So that may be a reason for you to use integer programming. It turns out that a lot of money are saved. So if you are having some free time, why don't you take a look at this article. Another example is this waste management incorporation. So this company pretty much is doing a recycling business. So, if you want to do recycling, you need landfill sites, you need waste-to-energy plants. Also that you can do some convergence, you need to have some facilities for you to do things. You need to have a recycling plant, transfer station, collection depots and so on. So when you are trying to collect all the things back to different planes, pretty much you have a lot of routes to be selected. If you are going doing the routing in a very weird way very inefficient way you're going to waste a lot of time with a lot of money. So, they construct a network with nodes and edges. And for each edge there is a binary variable saying that whether this route whether this age is included in a recycling route, okay? So if you want some concrete idea, for example, from here to there, maybe you have several different ways to do the routing, okay? Something like this. So if I have a network like this, I may walk in this way, that way, that way, and so on, and so on. So, somehow, there must be an optimal way, to do the routing. And that the way of doing that is for each link let's assign a binary variable. If that binary variable turns out to be solved and it will be one. We say it is included in your path or in your route. So certainly this again requires integer program, because if you get 0.3, 0.7 ,0.8 you have no idea about whether that link should really be included in your route. So again, a lot of money is saved and you may read article to help you get more ideas. So pretty much we are having all kinds of successful stories about integer programming. So, we will stop here about giving you a lot of application and the successful stories. All I want to say here is that there must be some reasons to use integer programs so that you use integer programs. Either it is because you have just a few number of persons or it is because you are making 01 decisions. If you just can use a linear program to do things just use linear program, okay? Today's lecture is for you to deal with those cases where integer programs, binary programs are really required. We will quickly see when that happens.
