Okay, our last part is about linearization again. But now we want to linearize the products of decision variables. In many cases, we may see products of decision variables, x times y, x_2, whatever. This can be linearized in some cases. For example, if the two variables, they are multiplied with each other, and as long as one of them is binary or both of them are binary. Then actually we have a way to take away that product. But unfortunately, if both of them are continuous, then there's no way to do that. If your x is continuous and you have x_2, no one knows how to linearize it. Probably there is no way. We will see some examples to show you how to do this, how to do this kind of linearization. First, let's consider this particular situation. Because we will have several situations. I'm going to label them as scenario 1A, 1B, or 2A, 2B, whatever. You will see why they are labeled in that way very quickly. Let's consider this example. We have a company and this company is making two kinds of products and they sell them to a market. There are limited resources. Pretty much if you look at this part, this looks very intuitive. You have limited resources. You want to make products and sell them to get some money. You need to have some consumption of resources. All these guys are non-negative, very typical resource allocation problem. Then making each product actually requires the setup cost. What is that? If you make product one, you need to pay $20 as your setup cost. If you make two, you need $25 as your setup cost again, very natural. Your z_1, z_2 are binary. Now the interesting part here is that, well, making both products can actually save you some setup cost. It's going to be that you have a factory. If you warm up your machine and hire some workers, wake them up, have them start work. That takes $20. If you do that for product two only, that takes 25. But if you have both of them worked, then you only need to warm up your machine once, you only need to wake up some persons once. Overall that saves you $10. If you want to make both products, you don't need to pay 45 as your setup cost, you only need to pay 35. I hope this makes sense to you. Now the thing is that we are having a binary program, and here we have the z_1 multiplied by z_2. Why is that? Because you may save this $10 only if z_1 and z_2 they are both one. If any of them is zero, you don't save these $10. So that's why you have a product term here. Z_1, z_2 is one, if and only if both of them are one. Now, this problem makes sense. Now that it's introduced to you how these may be linearized. For this case, again, that's introduced an additional variable, let's call it w. I'm going to replace z_1, z_2 by w. Then somehow I need to put this into the constraints. But I cannot just write it down into the constraints, that does not linearize anything. Now, we somehow play the same trick as if we are talking about those maximum-minimum things. Take a look at this. We all know that w appears in a maximum function so the function is going to push w to be as large as possible. If that's the case, then how about this? I'm going to say w is upper bounded by z_1 and z_2. W is upper bounded by z_1 and the w is upper bounded by z_2. Then what does that mean? Well, if z_1 and z_2 takes different values, then w, as long as w is upper bounded by both of them, here it'll be zero, zero, zero, and one. Only if both of them are one, then you may have your w to be one. I hope that makes sense somehow. Because once we play the trick, then we will be able to say your w will be formulated in this way. W of course, should be binary, and then you will be able to see that your w can be formulated in a linear way, as long as you split this guy into two inequalities. The last thing I want to say about this example is that your w actually can be considered as continuous. Because there's really no reason for your w to be 0.3, 0.7. You don't really need to set w to be binary. But of course, if you set it to continuous, it doesn't really matter too much.
