Welcome back to operations research. In this course, we talk about algorithms, and here we want to focus on integer programs. Last time, we talked about linear programming and we know there's a way to solve any linear programs. If we want to solve integer programs, that's hard because all the variables are integer variables. Now, you don't really have a full polygon that is feasible region. But if we want to solve a new problem and we have no way, what do we do? We look at old problems to see if there is any connection between the old problem and the new problem. We do have a way to solve the old problem. Maybe we may utilize and modify the original old solution and try to see whether it may be used to solve the new problem. The idea is indeed this one. Let's take a look. Basically, what we want to do is that I have an integer program, maybe something like this. I still have some concerns, but I now need to focus on integer solutions. Something like this. I know the graph is ugly, but anyway, you know what I'm doing. There can be a feasible region. Basically, inside this feasible region we have some integer points that are the really feasible solutions. In this particular case, if we're trying to move towards this direction, we have an optimal solution, which is this one. Some people say, I don't really know how to solve an integer program. Then how about this? Let's first ignore all the integer concerns and try to first solve its linear relaxation. Given an integer program, we're going to see whether it's linear relaxation may be solved. Given an integer program, I'm going to get its linear relaxation, which is a linear program. Given a linear program, of course, we know how to solve it. If we focus on this example, then when we want to solve this problem, its optimal solution would be this one. If that's the case, then we get a solution that is close to our optimal solution. But unfortunately, it is not. The blue point here is not really an optimal solution to our integer program because it is not integer at all. People say, well, that's not a big problem. This point, if you use numbers to represent it is roughly 2.3 and something. This 2.3 is not an integer solution. Then how about this? Let's focus on one solution where we required x to be less than or equal to two. Let's focus on another solution where we require x to be greater than or equal to three. In other words, given a linear relaxation problem, we split this problem into two sub-problems, let's call it LP_1 and LP_2. We will add two constraints. X less than or equal to two, or less than, x greater than or equal to three. Add these two constraints into the original linear relaxation and split that problem to two problems. Roughly speaking, in one of these two problems, you will have an optimal solution. Then this strategy will work. If you know how to solve LP_2 or LP_1 and once your solution is integer, that’s fine. If you solve LP_1 and it's solution is still not integer, is still fractional, then what do you do? You further split it. You further split all these problems until a solution can either be solved or you don't need to solve it. That's pretty much the algorithm we want to introduce today and it has a name. It's called branch and bound. We're going to tell you all the details about this branch and bound algorithm. Pretty much the idea I just mentioned, but we're going to use more examples to show you how it works, how we may execute this program, how we may utilize the idea of simplex method to solve integer programs, how these branching and what we mean by bond and so on, so on. This is going to equipped us with the tool to solve any integer programs. Then lastly, we will show you why this may be useful, but it may also be time consuming. We will also mention about the time complexity issue. Later. Let's start to do it.
