Hi, everyone. Welcome back to Operations Research. This is Ling-Chieh Kung, and today we're going to give you our third lecture. We're going to give you a new topic, which is going to be integer programming. When we are talking about integer programming, naturally is from linear programming, or you may say it's an extension, generalization, or so what. Basically here, we're going to allow you to have integer variables. That means you may restrict the values of your variables to be integers, to be zero, or one, and so on. In linear programming everything is fractional, everything is continuous, but for integer programming either may be discrete basically. We will see that it's going to be very useful. It may help us to formulate a lot of different things. For example, it may be used to formulate setup cost. What's that? In our previous week, when you are making some products, if you make one unit you pay five dollars, when you produce two units you pay $10. The cost is linear to your production quantity but sometimes it's not. Sometimes it's the case that, when you want to produce the first unit you need to pay a lot of cost, and then for each unit else you have an additional marginal linear cost. One example is that when you want to start to do something, you need to pay an advanced fee or you need to go to some where to setup your preparation. If that's the case, then we say you have setup cost or setup time. That's something linear programming cannot deal with, but integer programming will tell you how to do that. We have many different applications. For example, now you may do facility location. This is a very traditional and a very important decision to make when you run several companies. If you are selling a dialogue things to your downstream retailers and if you have a large scale, you need distribution centers, you need warehouses. Sometimes you also build your own retail stores. Governments they need to build hospitals, they need to build fire stations, they need to build post office. You always need to build facilities and you need to choose where to do that. That's something linear programming cannot do and the integer programming will tell you how. You may do machine scheduling. What's this? You have a factory, you have a lot of machines, and you have a lot of jobs to do. Each job must be processed at bio machine. You need to basically do some job allocation. Sometimes when you are facing this problem it can be very difficult, because you may face a lot of different constraints. You may have multiple machines, multiple jobs, and when you assign a job to a machine then the job must be fully processed by this machine. You cannot split the job and split it to multiple machines. Sometimes different machines have different capabilities. Sometimes different machines have different speed and so on. This job assignment problem, linear programming cannot do it, but with integer we can do it. We will also give you some examples about vehicle routing. Vehicle routing is basically some applications in logistics. If you want to do logistics, if you have a supply chain, if you want to deliver products to your customers, you need to consider vehicle routing or routing problems. Know these things are something that linear programming cannot do, and today we will expand our territory to deal with all these problems. They are important. There must be some way for us to deal with them, that's integer programming. All of these is basically doing one thing. They are doing selection, or some people would call it assignment. What do we mean by selection and assignment? Basically is that you need to specifically tell one person or one machine what to do at a specific time. For example, for machine scheduling you assign jobs to machines. You tell each machine at this moment what to do, at that moment what to do. If you want to do this job, you cannot do that job. At each time point, you select one job to do. For facility location problem that's pretty much the same. At each location, you either build a facility or not to build a facility, you select a few points to build your facilities. For vehicle routing problems, you have multiple routes to choose. You select one route to do it, something like that. You will see several examples and hopefully when you see each example in today's lecture, you will think about what are we selecting? What are we assigning? For last selection and assigning flavor, if you take a look at the inside of these problems you will always see selection, you will always see assignments. Those are the things that you may deal with, its integer programming. Later, let's see all the materials.
