Okay, so now we know what's linear relaxation. Now we want to see what's the relationship between that linear program and our original integer program. So there is the effect that is useful for minimization integer program is linear relaxation always give us a lower bound of its objective value? So more precisely, let's see what this suppose we have a minimization in future program. And once we find this optimal solution, we may get this objective value that's called z*. So z* is for that integer program. Okay, and we also have is linear relaxation. So we make a linear relaxation, we may also solve that linear program and get its optimal solution with objective value that's covariant z'. Okay, then the fact is that c prime is going to be less than or equal to z* For a minimization problem, okay, why is that? Well, it's actually very easy. So, suppose we are comparing these two program. This is an integer program. This is a linear relaxation. They have the same objective function. Moreover, The linear relaxations feasible region is typically larger than the original integer program, okay here you have a larger feasible region, because you are allowed to take fractional values. So if you are having a same objective function with a larger feasible region, then surely you will do better. And for a minimization problem, better means less than or equal to. So that's how our z' may be a lower bound of z* Okay? So somehow that means well if I give you a integer problem, if you don't know how to solve it at least you may solve it's linear relaxation. And then you will get some kind of estimation about your z* you don't know how to get z star, you don't know what's the value of z* but z* r cannot be that small or less large. Okay? So if that's a maximization problem then is the other way, linear relaxation will give us an upper bound. So you will later see this is very useful. Okay? So linear relaxation, it gives us a bump. That's good. But actually if we are lucky enough, the linear relaxation may either be infeasible, unbounded or give us some other solutions. So, that is some cases when we have an optimal solution which is feasible to the original integer program. So in all these cases, we may say the original problem has been solved. Suppose our linear program is infeasible then of course, the original integer program is also infeasible. Suppose our linear relaxation is unbounded, the original one would be also among them so both our conclusions if an optimal solution to the linear relaxation is also integer values. It happens that all its solutions are integers. Then in that case, that would also be an optimal solution to the original problem. Why's that? Well, let's take a look at the formal statement that say x prime is an optimal solution to the linear relaxation of an integer program. Suppose the x prime is feasible to the original IP, which means all its values are integers, it would also be optimal. So, this actually is a very general situation. Suppose you originally has a program where the feasible region is here, okay, you don't know how to solve this one. So you relax the program and get a larger feasible region, okay? And then you solve the relaxed program. If you see an optimal solution is here. It is not feasible to the original one, then is of course not optimum. But if you see your optimal solution is here is feasible to the original problem, then naturally is optimal because you are selecting a solution in a smaller set and you happen to select the same value. Then naturally If all the solutions in the yellow region cannot be greater than or cannot be better than this one, then all the solutions in the red region cannot be greater than this one. So that's the idea. So very quickly, that's the suppose x prime is not optimal to the IP. There must be another IP feasible solution that is better. But if x prime is IP feasible, then it would also be feasible to a linear relaxation and then your ex prime certainly cannot be optimal to that. So they are talking about the same thing just in an algebraic way or graphical way but now even though we have these lucky cases, we may still be unlucky. And actually most of the time we are unlucky. We solve the linear relaxation, get a solution and there are some fractional values. So in that case, naturally we will think how about this? Let's round up or round down the fractional values to get integer solutions, alright? So let's say we solve a linear relaxation and get a solution x prime. Sometimes we say this is LR optimal LR means the linear relaxation okay? So LR optimal means x prime Is optimal to the linear relaxation. However, we see at least one variable violating the integer constraint. So it may be 3.2 it may be 0.8 is not IP feasible, so it's not IP optimal. Then let's say we want to round the variable, then the question arises, do we want to round up, do we want to round run down? There must be some way to tell and to do this decision. And the resulting solution is it always feasible, probably not. And where the resulting solution be close to an IP optimal solution. Well, there's no way for us to tell. So here, let me give you an example. Suppose you have an IP which is here. So, the objective constraint they look very typical, you have integer variables and they should be non negative. So once you take a look at all those integer points Okay, you will see that the optimal solution is this one. The optimal solution is 5,0. And once we have that now let's take a look at LR solution LR optimal is to solve this linear program of which is the shaded area here. Alright. And if you do that very quickly, you will see that your optimal solution is 15 over four and then nine over four. The interesting thing is that if you do round up for both variables, your solution is not feasible, okay? And you may see that's true because these are less than or equal to constraints. You cannot just round up two variables. If you round up one solution, for example, round up x one, you're going to get four and a something. But then you may see that the four two is also infeasible. Okay, so that's also not a very good idea. Also, if we are talking about the other solutions, none of these are optimal solutions. Our optimal solution is 5,0, which is somewhat far from our x1 far from our LR optimal solutions, so that means if you roundup or round down that may create infeasibilities okay? In this particular case If you round up just one variable and keep the other variable unchanged, you're going to be here or here or if you round both, or if you round up just one of them and the round down the other way, there are so many possibilities for you to get infeasible points. And even if you try all the integers solutions around your fractional solution you still don't get an optimal solution. So, that means solving a linear relaxation and then to rounding is not a general strategy. We need some more and that would be friendship bond.
