Let's start with a major idea. That will be the heart of a lot of things. That will be linear relaxation. Let's say, we want to solve an integer program. Suppose we are given an integer program, how may we solve it? We know that the simplest method now does not work, because previously when we are talking about the simplex method, your feasible region is really a region. But now instead, you are having some discrete points. For example, if we are talking about the integer program here, well, this is a linear objective function, a linear constraints. But now you are x_1 and x_2 lay must be integers. So here we have a notation, Z plus. Z is the set of integers, and adding a plus here means there are non-negative integers. So if that's the case, then your feasible region is the set of this one, this one, this one, this one, this one, or you get several points that are feasible, but they do not really form a region. In that case, there's no way for us to move along edges. Maybe we need some other ways, but we all know that we don't really know a lot of things. For operations research, for mathematical programming, the only systematic method that we have learned is the simplex method. Maybe we should find some connection between integer programs and a linear programs to see whether the simplex method may help us. How about this? Let's try to solve a linear relaxation of our integer program. So what's that? Given an integer program is linear relaxation is the resulting linear program after we remove all those integer constraints. If we take away these integer constraints, we get it's linear relaxation. Previously, we are talking about some integer variables or integer programs. In that case, now we want to do linear relaxation. All we need to do is to take away that integer constraint. Here, don't forget when we say x_i is in Z plus, that means x_i is in Z and x_i are non-negative. When we do relaxation, we only take away the integer constraint. You still have that a non-negativity constraint. It should be still there. If you take away the whole thing here, then you're wrong. You must make x_i remain non-negative. Also, that's linear relaxation. Similarly, suppose we have a knapsack problem where we have four items to choose from, the knapsack capacity is 10 and the weights are 5, 7, 4, and 3, we need to pick a few items to make sure that we don't exceed the knapsack capacity, and we want to maximize all the total values. Originally, it should be binary decisions, so all your x_i are binary. Once we do the linear relaxation, the less than or equal to 1, should still be there. Greater than or equal to 0, should still be there. It's just that previously, you may only take values with either zero or one. But now you're region becomes the whole line segment, we're seeing zero and one. Now, your x and may be 0.6, 0.2, whatever. In that case, now we have in effect two constraints remains, but we don't have that binary variable or binary constraints. That's linear relaxation.
