We have all the understanding about models analysis. Now let's jump into modeling and then try to see what do we mean by mathematical programming. In this course, we will have several other weeks. They will have different topics, they will have different focus. But basically, all we are doing is mathematical programming. In this video, I'm going to give a very brief idea about mathematical programming. The example may be very simple, but the idea is pretty much the same with all other complicated models. The example is here, and this example is a very classic example, is called the knapsack problem. If you are studying computer science or something, you may have heard about this problem. But if you are not, there is no problem because the problem is very easy to understand. Let's say you want to go for hiking tomorrow, and you are thinking about what to bring into your backpack. Knapsack is another way to call backpack. You have a bag, you want to put something inside so that tomorrow when you go for a hiking, you have something to use. You may want to bring your compass, you may want to bring matches, you may want to bring telescope or you may want to bring your Rilakkuma. There can be all kinds of options, but unfortunately, there is a limit. Your backpack can only carry at most five kilograms of items. You may think about that limitation as the limitation on your backpack or on your body. Maybe you are not strong enough, you cannot carry everything. Anyway, there are some things. They all have their weights. The total weight is more than five kilograms, so you need to think about what to bring and what not to bring. The total limit is five kilograms. The sum of the weights of your carried items cannot be greater than five kilograms. You also know that all these items have some values. You will want to bring those items, bring as many items as possible so that you may maximize the total value of the items you bring. For example, you may think, compass is very light and the value is so high. Probably you want to include this one. If you think about the cylinder is heavy and the value is okay. You need to have some trade off between weights and the values. You need to consider both information to make your decision. The last thing is that items cannot be split. There is a compass, you split into half and bring half into the mountain, then it becomes useless. So items cannot be split. For each item, you either choose it or discarded it and you want to maximize your total value subject to a constraint that the total weight must be limited. I just made some description about this problem, but probably you also agree my description is not so precise in some sense. Whenever people are using words to describe a problem, there must be some ambiguity. My description and your description may be different. The way I interpret my description may be different from your interpretation. Words are good but if we want to communicate with computers, models is needed. In that sense, we're going to later tell you a model that can help us solve the problem and the find the best of combination. But maybe you also think about why do we need a model? Here lets have another perspective. You'll try to solve this problem. You'll say, how about this? I'm going to calculate the weight value ratios for each item. I'm going to calculate the weight over the value, over weight value. For example here, what is 12? Twelve is 6 divided by 0.5. That's some benefit ratio. I calculate. What is 10? Ten is 4 divided by 0.4. Intuitively, if this ratio is large, that pretty much means this item is valuable. It has high value and a small weight. If I bring that, that should contribute a lot to this problem. I may calculate all the things and then do some sorting about the items. This one looks very good. I'm going to bring this one. Ten is also high, so I'm going to bring matches. Then the next one is 4, and then 3.33 and then 2.75. If I go through this process and pick the top five ration items, I'm going to bring items 1, 2, 3, 4, 5, and I will stop because I have no more room to bring more items. The total value would be 22. But if you have some time, if you use 30 seconds to think about this again, you are going to see that the better solution, the optimal solution is actually to bring items 1, 2, 3, 4, 6 instead of 1, 2, 3, 4, 5. You may actually do better than using that simple rule. Basically, with these two pages, hopefully, I tried to convince you about why do we need a model. Previously, the reason is, I want to have a precise description about the problem so that a computer may understand. In this page we add another reason, because if the problem is complicated enough, if you have millions of items, then your simple rule may not work. Your simple rule may fail to find an optimal solution, but with a model, computers may help us find a better solution. Let's see how to do this. Let's see how to model or formulate this problem. Turns out it's very simple. First, we need to define decision variables. Decision variables means they are something that we may control, something we may determine. In this case, we may determine whether we want to bring item i, so we are going to define xi as a (0,1) variable. If I want to bring item i, I'm going to set xi to be one. Otherwise, if I don't want to bring item i, I'm going to set xi to be zero. So I have x1, x2 up to x7. If I have this set of decision variables, then I may write down a so-called "objective function". This is to describe what do we want. We want to maximize values and then we can write down this function like this, If I bring item one, I may get six points of values. If I bring item two, I can get five points of values. This expression here is that according to the (0,1), (1,0) I assigned to these decision variables, I have a solution. I determine what are the things I want to bring and then, that can calculate the total amount of values I may generate. The next thing is about constraints. A problem typically has some constraints and that limits the number of options we have. In this case, the limitation is that the total amount of weight of my carried items cannot be greater than five, the maximum limit of the backpack capacity. This particular expression is that, if I bring item one, it consumes 0.5 kilograms. If I bring item two, it consumes 1.5 kilograms. The left-hand side of this expression is that according to the (0,1) I assigned to these variables, I know what's the total weight I carry. The total weight I carry cannot be greater than the total amount I may carry. So this is my knapsack constraint. Finally, we have this thing. Here are some mathematical symbols. This means for all, or for each. For each i, that is one or two or three or four, we have a constraint, says xi must be in the set zero or one. This means your xi can either be zero or be one. It cannot be 0.5, it cannot be three, something like that. For each value, for each variable, you assign either zero or one to this particular value. Collectively, we now have a formulation or we now have a model for that Knapsack problem. We have seven variables, x1 up to x7, each of this variable is zero or one. You don't know whether it should be zero or one. The model after we solve it will tell you. Then you have a constraint saying that the total amount of weights of your carried items cannot be greater than the total amount you may carry, and that you want to maximize the value of your carried items and that's the model. Once we see these model, it is precise. You formulate this problem, I formulate problems, the result will be the same. Your interpretation, my interpretation will be the same. Computer will also understand these formulation. That's why we say a mathematical model is a precise formulation. Once it is precise, a computer may understand it, a computer may solve it with some algorithms and then it's going to help us understand what would be a solution that may be better than any other solution that people may generate. So that's mathematical modeling. The model is good and we see a model here but you may also have a question in mind. You may think that, oh, well, if I have 70 items, what will happen? You are going to have a very, very, very long expression here. What if I have 700 options, very, very, very, very, very long expressions. There must be some more efficient way for us to formulate a problem like this, so we will use some more mathematical notations to help us to do this. This is how we do a compact formulation. Let's [inaudible] notations. For item I, actually I don't really care about whether the weight is seven or four or two. Let me call the weight of item i as wi. All right? Then, let me call the value of item i as vi. Here they are just symbols, but you know they have their concrete numbers. For item one, the value is seven. For item two, the value is six, something like that. Then your v1 would be seven, v2 would be six and so on. Let n be the number of items, then your n would be seven. Let B be the maximum allowable weight. Then in this particular instance, B will be five. After we have all these notations, we may have a compact formulation like this. That may explain what's this. Basically, this is saying that I want to maximize my total value. Here I have a summation. Right? Summation i from one to n. For each i, I have v and x multiplied together. So when i is one, this is v1, x1, when i is two, this is v2 x2 and so on. Then lastly, we will have vn xn. If we collect all of this, that's going to be my total value. According to the assignment of xi, I have this particular total value. Then these particular expression, as we learned in high schools, can be abbreviated into this summation notation. This is the total value we generate. Similarly, we have these particular expression as the total weight we must carry. V as wi is the weight of item i, according to whether you choose item i or not, your xi will be one or zero and that's going to determine whether you need to bring xi into consideration. After we get this summation, we know what's the total amount of weight we carry. It cannot be greater than the total amount that is allowed. The second expression here is that capacity constraint. Then lastly, this is the same as previous. For each item up to item n each variable can only be zero or one so that's the formulation. If you look at this formulation for your first time, this may be a little bit weird or scary, but it turns out that this is just the same as the previous formulation in a more compact way. If you have multiple items, you have medians of items, there is no problem. The formulation is still like this. This obstruction is very good. Why is that? Because it not only save us some space, it also helped us to generalize this formulation to other applications. Probably you don't care about hiking, but probably you are running a company, you are running a factory. There are several orders. Your products very popular so there are a lot of orders from all kinds of consumers. They all want your products. They say, "Hey. Why don't you make 10 units for me and I'm going to pay you $10." "Why don't you make 20 units for me and I'm going to pay you $30" Something like that. Different companies place different orders and the different orders have different total amount of time you need to spend and a total profit you may generate. You'll see a lot of orders, you are happy. The total number of orders is n, but you have limited capacity. Your factory is just there. You cannot do all the orders because your factory capacity is limited. The total processing time is limited. Then in that case, the formulation would just be the same as the Knapsack problem. You have several orders, you cannot take all of them. You want to take some of them. You want to maximize the total amount of profit you may generate subject to limited capacity. If all these orders cannot be split, then you need to solve this problem. That's exactly the Knapsack problem. One formulation can be applied to multiple problems. Or think about portfolio optimization. In this video, we're talking about very typical problem. Its about when you have several units of money, then you want to allocate them. Here let's consider a very simplified version. Suppose you have several stocks to choose and you have limited budget. You want to buy all of them, but you don't have another money. You consider the possible investment amount for each product or stock, and you consider their expected return. You want to allocate your money to those stock that may generate a return for you. You calculate this information and then you try to solve this problem. For each stock, the maximum possible investment a month is wi of five million dollar, seven million dollars. In that case, your x_i now should be interpreted as the percentage of that maximum possible a month that you'll want to spend money on it. For example, if w_1 is five million, then if x_1 is 0.5, then what does that mean? That means you want to invest 2.5 million to stock one. That's the meaning of this particular formulation. For each stock, each investment option, there is an upper bound. You determine what's the percentage of that upper bound that you want to invest in. If that's the case, then the left hand side, again, look like the previous formulation, is just the total amount of investment you make. It cannot be greater than total amount of money you have. According to your investment, that's going to generate value for you. Again, this probably is pretty much the same as order selection as knapsack. The interesting thing here is that you can see, this is different from the previous formulation. Previously, we write x_i should be either zero or one. But here we write x_i should be within zero or one. Because if the maximum possible value is five million, no one says you cannot invest four millions, three millions, and so on. You may determine a value within this range instead of zero or five million, you can determine a wrench. In that case, your x_i can be any fractional value within zero or one. Basically this is because your investment decision is not all or nothing. When you are thinking about whether you want to bring your compass to do a hiking, that decision is all or nothing. You either bring it or not. When you are thinking about whether to accept the customer's order, the order decision is zero or one, all or nothing. But for investments it's not. In that case, we write it as within zero or one, not must be either zero or one. This allows us to do some comparison between these two models. When we say your variable can be fractional, when we say your variable must be within a wrench falls into an interval, we call this problem as a linear program. On the other hand, if your variable must be an integer, must be discrete, must be zero or one, we say this is an integer program. These two formulation, or these two programs are, I should say, similar but somewhat different. You may see that this part and this part, they are exactly the same. The number of variables is also the same. It's just that whether you may be fractional is different in a linear programming problem, just like that portfolio optimization thing, in that case, your variables can be fractional or when you want to determine the number of orders to accept when you do that knapsack problem. That's an integer programming problem because you either bring an item or not. We are not here to go to details about all the things, I just want to use this example to tell you there are different kinds of mathematical programs. We need to use a course, like this course, to use different weeks to tell you what's the details about different programs. They are linear programs, nonlinear programs, linear integer programs, nonlinear integer programs, and so on and so on. Different kinds of programs can solve different real problems. Sometimes we solve nonlinear programs, sometimes we'd solve integer program from time to time. We need to look at the real problem and choose the right tool to deal with it. Sometimes we should use linear programming, sometimes we should use integer programs, sometimes we should use nonlinear programs. We will spend some time in this course to take a look at all these possible tools and then try to give you all kinds of applications to tell you, for this application, do this for let application, do that. Through this process, you will get some experience about how to use mathematical models, mathematical programs to solve real problems.
