All it remains is for us to deal with the remaining three scenarios. Let's say a company is going to make two production processes, and then that's going to fulfill a demand for two products. But the company should do that only if it accepts an order. What does that mean? It means that now the company needs to make a decision about z, which may be 0 or the 1. If z is 1, that somehow means the company is going to accept an order, and then that's going to earning of $50. That's one thing. But once you accept this order, you must make some products to fulfill the demand. The demand is here, 6 and 8 for product 1 and product 2. You'll need to somehow determine the amount of hours to run your production processes. Then that's going to have some consumptions, and eventually that's going to tell you that you need to pay some cost, about this. You're going to see that, if you don't accept this order, saying that if you put z equals 0, then somehow you still need to make the production planning, but you don't need to execute it. That means you don't need to pay any cost, actually, as long as you don't accept this order. There must be some way for us to linearize this particular formulation. Here, when you take a look at this formulation, the non-linearity appears at the maximization objective function. We somehow are maximizing negative 10 times x_1z, minus 12 times x_2z. We have some other terms, but the non-linearity appears here. Somehow we may see that, if there's no limitation on x_1z and x_2z, say if we replace this guy by, for example, w_1, replace this guy by w_2, naturally, if there's no restriction on w_1 and w_2, we will try to make w_1 and w_2 as small as possible, so that we may maximize our objective functions. That give us a very quick suggestion. It says that, our reformulation need to give some lower bound on w_1 and w_2. Let's see how to do that. Well, we still do the introduction about w_1 and w_2, according to the way I just mentioned. Here, x_1z is going to be replaced by w_1, x_2z is going to be replaced by w_2. For this some kind of minimization objective function, we should have a lower bound. Let's try to play this trick. We're going to say, w_1 is going to be greater than or equal to x_1 minus 8 times 1 minus z, and then w_2, pretty much the same thing. Let's take w_1 as an example to see how this works. We know w_1 is lower bounded by the formulation we just provided to you. Let's say z is 1. Suppose z is 1, then in this case we can see that our w_1 must be greater than or equal to x_1. That somehow means, as long as you make some production plan, as long as you run your production process for a few hours, you need to pay that cost accordingly. As long as you accept that order. That's one thing. On the other hand, if we say z is 0, then that constraint should somehow disappear, so that we don't need to pay anything in the new formulation. If z is 0, then our constraint on w_1, would become w_1 greater than or equal to x_1 minus 8. This seems to be a constraint. But actually if you take a look at the original formulation, immediately you will see that your x_1 has no reason to be greater than or equal to 8. Why is that? Because as long as you set your x_1 to be 8, it is enough to satisfy everything. There is really no reason for you to run this production process, to be more than 8 hours, in some sense. If x is actually less than or equal to 8, then very quickly you'll know the right-hand side here is a negative term, or non-positive term. If you also have w_1 greater than or equal to 0, then in effect, this particular constraint disappears. That somehow tells us why we choose 8, to be the coefficient here. Because after the analysis on the original formulation, we know x_1 is upper bounded by 8. That's why we set 8 to be the coefficient here. If you have no other ideas, you may set this 8 to be a very large number. But, of course, if you have a precise estimation, that will be better. We play the same trick on w_2. Then eventually we will have a new formulation which is linear, and which may still represent the original situation. Now, the remaining two situations is for the product term to appear at the constraint. Suppose the product appears at a larger side, then it will be a situation like this. Our x_1z, in this particular example, is greater than or equal to something. Suppose that's the case. Again, we try to linearize it by doing the replacement. Let's say w equals x_1z. In this case, w would need some kind of upper bound. Otherwise the formulation does not make sense. Now, you need to give w an upper bound, just in a very familiar way. In this case your w is less than or equal to x_1, and then w is less than or equal to 10_z. What does that mean? In this particular case, if your z is 0, then somehow that means your w should be 0. Because w is x_1 times z. Your w would be less than or equal to 0, and then that allows you to result in a 0 for your w. If your z is 1, on the other hand, then in that case, you're going to require yourself w to be equal to x_1. Then in this case, because your z is 1, in some sense you are going to remove the second constraint. Why is that? Because according to the original formulation, you know there's no way for your x_1 to be greater than 10. Somehow that means, if your x_1 can no longer be greater than 10, then in this case, once you set your z to be 1, then this second constraint, in some sense, disappear. It's not effective at all. Then we're going to have only the first constraint, which says w cannot be greater than x_1. Then that somehow allows us to set w to be equal to x_1. That's how we do this. Lastly is a case where our product term appears at the smaller side of a constraint, like this. Again, we want to replace that x_1z by w. Our z is binary. Again, we apply the same trick, saying that our w should be greater or equal to x_1, minus 10, times 1 minus z. We would also add another constraint saying that w is greater than or equal to 0, naturally, it's because our x_1 is non-negative. Let's take a look at how this works. Your z maybe, for example, 1. In this case, a constraint here is going to be w is greater than or equal to x_1. If w is required to be greater than or equal to x_1, then according to this formulation, you are going to set w to be as small as possible. Then that's going to be in effect w equals x_1. That allows us to sell w to be equal to x_1, as long as our z is 1. That's one thing. It's also possible that our z is actually 0. If our z is 0, this constraint becomes w greater than or equal to x_1 minus 10. According to the original formulation, we know our x_1 cannot be greater than 10. That's why we have 10 in the new formulation. If our x_1 cannot be greater than 10, then the right-hand side here, x_1 minus 10, is going to be non-positive. Then because we have w non-negativity, so in that case, the non-negativity constraint is going to terminate this constraint. That constraint actually disappears, and our w can be greater than or equal to 0. To make w as small as possible, w will become 0. Again, that makes w being equal to x_1 times z. That's how this reformulation works.
