Okay, so now we are at our last stage for this lecture. We now want to introduce compact linear programming formulation. So the thing is that for most of the problem instances that we need to solve in practice, they have large scales. Somehow that means you have thousands of variables, millions of constraints, and so on. That's very typical. Because if your problem is simple, you use a hands papers by yourself. If your decision is not optimal, typically it does not hurt too much. But if your instance is really of large scale, if you are really running a very big business, then the number of constraints, number of variables will be too much for you to write down all the numbers, that's impossible. So you need to have a more efficient way to write down formulations. For example, you'll make group variables, right? When we say xx is the production quality of date t, that's the grouping. You will sometimes also group constraints, like you may write xt is non-negative for all t from 1 to 4. You are not going to write down x1, let say greater than or equal to 0, x2 greater than or equal to 0, and write it four times, you don't need to do that. So, when we really need to model large scale instances, we use compact formulation to enhance readability, efficiency, and actually the degree of abstraction. So very quickly, we will show you how to use the three instruments, including indexes, summation, and for all operators to help you write down compact formulations. We have two examples, and let's do the first one. So, we want to revisit our production inventory problem, so we know we have several periods. In each period, we produce and then sell, unsold products may be carried as ending inventory, we want to minimize the total cost. If you only have four periods, it does not hurt too much to write things down explicitly. What if you have 90 days in a season, right? What if you need to plan for the following year? Then you have 365 days, you need to write down so many numbers, there's no way to do that. So let do compact formulation. The first thing is always to consider indexing or indexes, all right? So things would repeat, items would repeat, periods would repeat. So pretty much, we may say, is going to be the case that when you have some repeating thing, your indexes may help, okay? So we're going to let t be the index for this particular problem. t is from 1, 2, 3, 4, or if you have 90 days t is from 1, 2, 3, up to 90. So now that simplify our objective function with the idea of indexes. Once we have t, if we replace all these 9, 12, whatever numbers by Ct, where Ct is the unit production cost on day t, then our objective function is simply this one. We want to minimize the total cost, okay? And we have this summation, t goes from 1 to 4, so we have C1x1 + y1 + C2x2 + y2, and so on, and so on. And a C1 is 9, c2 is 12, very quickly, you may see, all we need to do is to write a very short sentence or very short expression to see that this is indeed our objective function. And immediately you may say what's the point of doing this? If this is not 4, if this is 400, the statement is pretty much the same, you don't need to write a very long expression. For constraints is pretty much the same because always they share some similar patterns. So for the constraints, we have these originally four constraints. Now that again make some notations that say the demand of day t is Dt, okay, t from 1 to 4 again. Then for each day except the first one, we would say yt- 1 + xt- Dt is yt, for day t, yt- 1 is your initial inventory, right? Plus the amount you produce minus the amount you sell is your ending inventory, but don't forget we define yt as our ending inventory. So, we somehow cannot apply these to day one, 2t is 1, why is that? Because if you apply that is going to be y0 plus x1, blah, blah, blah. But y0 has not been devised not being defined. If you do that, this would be just similar to what you do when you are writing computer programs. If you write C++, if you write Python, if you write whatever computer programs, if you use a variable that you have not defined, that's syntax error, the program is just incorrect. So, if we want to group all these four constraints into one compact constraint, let add one variable y0. Y0 is added as the ending inventory of day 0, somehow that just means the initial inventory for day one, right? So physically, there's no problem, we just did technically add that into our notation. So t goes from 0 to 4 instead of 1 to 4, so this is again something I need to emphasize. When you are doing your definition, don't forget to write down the in texting terms because that's important. If you don't have that, your program is just wrong. And then the set of inventory balancing constraints may be all collected in a single sentence, of course, you may need to set up your initial inventory. So now this is our compact formulation. We can see that we are minimizing the total cost, we have four inventory balancing constraints as we mentioned, we again have the set of non negativity variables. And lastly, y0 is set to be 0, because initially we have no inventory, okay? So we may see that here. This is a very compact formulation, saves a lot of spaces. And if you have 400 or 4000 periods, then it's going to save you even more time and the spaces. So that's pretty much one of the very beginning reason for using compact formulation because you must do that when you have a lot of periods, a lot of products. So do not forget to write down those four statements, this one and that one. At the beginning, many students they just forget to write these down, well, it's just going to hurt you, because if you don't have that your formulation is wrong. And when you really need to convert your mathematical program to work computer program, that a solver can solve, you always need this to be specified, to specify the thing to computers. So why don't you do it when you are writing down your mathematical formulation. Okay, another thing that is somewhat minor is that when you have xt nonnegative, yt nonnegative, many people don't write the non negativity, twice,, three times, four times, they just collect everything together. I believe that's fine. Finally, there's one thing that many people do, but again, not required. Many people would use lowercase letters for variables and upper case letters or capital letters for parameters, that help everyone to clearly understand what are parameters, what are variables. Also, that's okay, if you feel this is a good idea, you may follow. But I will say many scholars, they also don't follow this, because when your program is really complicated, this may not be easy to follow, also it's up to you. Lastly in this example, I want to talk about parameter declaration. So when we are creating parameter sets, sometimes we write things like this, right? Let's denote Ct as the unit production cost on day t for each t from 1 to 4, something like this. Again, when we are writing down the formulation like this, you don't need to specify values even though we do have those values. When you are writing down this notation definition, you don't need to specify, C1 should be 90, C2 to be 100, you don't need to. Because you still have too many values, there's no reason to do that, okay? But you need to specify the range 1 to 4, you need to specify that through the index, otherwise your definition again is unclear. Parameter declaration or parameter definition should also be placed before you write down the formulation, right? Otherwise, no one knows what's your Ct, what's your Dt, and that would be weird. Finally, just a reminder, parameters and variables, they are different. Variables are those things that our program should tell us the value, all right? Variables are those things to be determined by solving the problem. We don't their values, we don't know how much to produce, we don't know how much to sell before we solve the model. However, parameters are given information. We know their values, we take these values as given to formulate our problem, so that we may really solve a problem or a problem instance. Some people will say parameters are exogenous, okay? They are fixed, they are given, and the variables are endogenous, they can be determined by ourselves. Okay, so you may see these terms from time to time, don't forget to link them to their correct ideas. Parameters are exogenous, they are fixed, they are given. Variables are endogenous, they are to be determined.
