So that's the end of the studies of algorithms. So we're not done for all the algorithms, but we have covered the most important ones. Now let's talk about what we want to do in the next course. If you already learned models, applications and algorithms, what else should you do? So in my opinion, basically when we are learning operations research, we want to learn how to solve problems. To solve problem you need algorithms and a good algorithm does smart search. What does that mean? A problem is hard because there are so many options. So many solutions. You want to pick the one that is optimal. This is difficult. So if you know nothing about the property of an optimal solution, you need to ask everybody about, is your optimal, that's too time consuming. So basically, you need to know something about an optimal solution so that you are able to do a Smart Search. You don't need to search among all solutions. You just search among the solutions that satisfies the condition you need. So the key of being smart is to do some analysis. Before you really try to solve a problem, you need to understand the problem, you need to take a look at the problem as deeply as possible. To ask yourself for example, what are some necessary and sufficient conditions for the solution that you are looking for? So basically, in your everyday decision you are doing this. For example, if today, you want to decide what to eat for dinner, you want to choose a restaurant. That's also an optimization problem, right? Because you want to optimize the utility, the feeling, the happiness you have after your dinner. You consider a lot of things, you consider the price, you consider the service level. You consider the distance from your location to the restaurant, you consider whether your friends want to eat with you or not. Something like that. Somehow, there are just so many restaurants around you. You don't consider each of them one by one, because that's too time consuming. You will very quickly ask yourself, what are the things that must be satisfied for a solution you want to choose for tonight. For example, if you want to eat with your friends, you ask them, hey, what do you want to eat? They say, I don't want to eat McDonald's or then you cancel McDonald's. Or if they say, I want to eat something that is blah blah blah is tasty or does not have ice cream or blah blah blah, you will list those conditions that must be satisfied by the option you want to choose. And then you can quickly focus on feasible options or focus on good enough options. So, coming back to operations research, if a linear program has an optimal solution, we know it must has an extreme point optimal solution. This is very useful because it help us to focus only on extreme points. If there is something I want to choose, there must be something within the set of extreme points. So I only need to focus on this part. So my algorithm can be designed to only focus on this part, on that simplex method. So, if you want better algorithm from time to time, you need more useful properties about linear programming. So in the next course, we will focus on this kind of design idea, focus on analysis. We will have a lecture telling you what are more properties about the optimal solutions for linear programs. For other kinds of programs, that's the same thing. For integer programs, for example, we know linear relaxation is a key, typically is the first step. And we really want that for this linear program, after relaxation, we get a linear program. We are able to solve this linear program. We really hope the LP optimal solution can be integer solution, but that sometimes it's true, sometimes it's not. We want to ask, is it possible for an optimal solution to the linear relaxation to happens to be feasible to the integer program? Is there any kind of condition that can ensure this to happen? Or if we may find such kind of condition, then we are very happy. For that kind of problems, just use linear program to do it, we are done. So maybe that happens, maybe that does not happen. We are able to give you one lecture to talk about for what kind of problems we are able to apply this idea, for what kind of problems, we may have a condition to ensure that you would just need to use linear programming to solve your integer program. Your linear relaxation is precise. For nonlinear programs, we also have a lot of different things to do. For example, gradient descent keeps us doing all the improving things until it's filled that the first order derivative is flat enough, until he thinks the slope, the improvement is flat enough. But it happens that sometimes gradient descent does not give us an optimal solution. Sometimes you have a program like this. You get to a place where you feel that there is no improvement because you already get to a place where the derivatives is flat, but actually there is a better optimal solution. So we need to have some ways, some theories to help us categorize problems or to help us understand, when gradient descent gives us a global optimal solution, when it's not. So briefly speaking, we need more tools. And when we are talking about more tools, now what we need is theory. We need to go deeper to those mathematical properties. We need to have more mathematical tools. So that we may have better analysis on the problems we want to solve, and then have better design of algorithms. We need to have some ways to rigorously investigate the theoretical properties of given mathematical models. So that's the heart. That's the core for our third course is about theory. We will give you a lot of ideas, the keywords are listed here. Shadow price, duality, total unimodularity, convex function, convex set, Lagrangian, blah blah blah. All these keywords, all the ideas will be mentioned in the next course. We will tell you what are them, how to use them, and how these ideas may help us verify whether an algorithm is good or design good, better algorithms. We need these theories to help us improve ourself, improve our algorithms. We will try to show you how these theories are useful and the more importantly, maybe how they are so beautiful, how they may solve things in a such a pretty way, how they may help us get to the next stage. So that's pretty much all I have for today's lecture. That's also the end of this called course. So if you are still interested, now let's see you in the next course., thank you.
