Okay discrete optimization or greedy algorithms. So what we want to do in the next two lectures is basically cover greedy algorithm which is essentially the first step. You can always try it when you are trying to solve an optimization problem. Okay? Very simple, okay? Heuristic, mostly, no guarantees. But it's the starting point, okay so what we want to define is what is a greedy algorithm and then you know very informally, right. And then essentially how to go beyond greedy and that's the things that, that's essentially what we going to cover, okay? So, so the, the biggest assumption that we are making in this lecture and the next one is that its very easy to actually find a feasible solution the real problem here is optimizing, okay? So, when it's tough to find feasible solution you know, we, we can use other techniques and, and some of them I'll discuss in, you know constraint programming or local search to actually transform that in a, in a problem where the finding the solutions are easy, okay? But here we are basically assuming that finding a feasible solution is easy, okay? We focus on the objective function. Okay, and the key idea behind a greedy algorithm is that your going to look at the variable, the decision variable one step at a time okay and your going to assign a value for every one of them and in a sense you choose that value to minimize the value of the objection function, locally. Okay at this point your choosing a value such that the objection function increase the least. If we are minimizing. Okay? So in a sense, we are looking at the particular variable, we are trying to assign a value, and minimizing the impact on the objective function. That's what the greedy algorithm here, okay? Now called greedy algorithm or heuristic, you know, essentially they are basically making decision one at a time based on local information. Okay? So we're going to illustrate that on the TSP problem. The TSP problem is one, is probably the most famous combinatorial optimization problem. Okay? And the key, you know, the key aspect of the traveling salesman problem is that you have a bunch of cities that you have to visit and you have to visit them exactly once, okay? So you have to move from one city to the next and so on. You visit them exactly once and what you want to do is minimize the travel distance that you have to travel for you know, visiting all these, for visiting all these sites or these customers you can think of. Okay? So this is a solution to the travelling salesman problem okay, so you start here, you know you, you visit this, this, this particular city you go the next one and you follow this very nice path and that's essentially a solution to the travelling salesman problem. Every city is visiting, is visited exactly once and then you measure you know the distances that you are travelling and that's what you are trying to optimize, this is another solution it looks better or probably shorter, okay And so this is once again, you visit all of the cities once, okay? And in this particular case it seems that the distance is smaller. I haven't computed it, but it looks better. So now, what is the greedy algorithm going to do? So once again, what we want to do is build a solution step-by-step. So we start from the vertex and we know that, that vertex, that you have to go to some place from that part of the vertex, okay? So that part of the city, okay? So we take the, you know we take its closest neighbor okay, and that's where we going to go. So you say okay, we start here and we go there. That's the closest neighbor, Okay? Then in the next step we are basically saying, okay so you know what is the we, we, we, we have moved to this particular position and we ask us that exactly the same thing where is the next place where I can do, where I can go which is going to cost me the least, okay, what is the nearest neighbour, okay and so in this particular case you got to that particular you know you, you go to that particular location once again, you repeat the process: you say what is the nearest neighbor where I have to go, ok? In this particular case you can say, "Oh, but it's this guy." So you can visit this city only exactly once, so you will be able only to go back to this [UNKNOWN] the first location. When you have visited everything else okay so what is the nearest neighbor which is not something that I have already been too okay. And that brings you to that particular location and then you continue okay. And you built this beautiful tour here okay once step at a time and when you arrive to the last location. You just return to your starting point, okay so that's how you do a greedy algorithm with everyone of the step you are looking oh, what is the next city that I can visit which costs me the least, okay and does the idea of the nearest neighbour, now you look at the students here but this is pretty good, right but you know of course that these problems are [UNKNOWN] hot so there will be cases were these things are not going to be good, this is one example, okay same instances but we just changed a little bit the position of two vertices Okay, and the key idea is that we have done this maliciously, right, just to make sure the greedy algorithm is not going to work. What's happened, you know, you start from the same place, you visit the first thing. You get to this nice location there and then you take the, you know, the closest location to nearest neighbor to that particular location. And it's not this point because it has moved, no? It's this point, so you go down and you do the same thing at this point, this is the closest neighbor so you go there, and this guy now is left alone at this point. OK? So we don't really know when we are going to visit it. We continue, we think we are doing the right thing at every point, and then we get to this point. Usually at this point we would like to go back to the depot but we can't, right? Because we haven't visited all of the cities. So we are forced to go back to this long location that we avoided going to before. And then we have to go back to the depot. Now you see that this is a terrible tour of your state, because we have many crossings, and you have this long-distance trip here which I completely avoided. So this is where these greedy algorithms are breaking. They're going to work sometimes, and they're not going to work other times. That the essence of these, these algorithms. There are many greedy algorithms, this is another one, which actually has some performance guarantees, okay, not very good one in metric space but they have some. Okay so the key idea here is that, instead of moving from one vertex to another one, from one city to the closest one. Here we are going to build the two with two cities and then we going to extend it to three cities, and then four cities, and then five cities and so on and so forth, okay? So we basically look at this particular, this particular two with two cities here, okay and now we select another city lets say this one, okay and we are basically asking you asking ourselves okay what is the easiest way to actually insert that particular city, okay? And the basic idea here is that we have to remove this edge and insert to other edges, okay and now we have a two wishes three cities and what we have to do next is try to insert another city, okay? So we are going to consider this city and we are going to say oh, you know what is the best way to insert that particular city. And by best way, what I mean is that the cheapest way to insert that city, okay? Now you may say, oh, but that seems to be very complicated, but it's not right? So there are only so many place where you can actually insert this, this particular city, right? So you can say oh, I'm going to go from here and then back there and then go back here. Or you can insert in between of these two. You can do this, and then go there or back there, okay? Or you can go actually from here. To this, and then go there, and then you have a tour of four cities, and this is actually a better tour in this particular place, okay. So what you are trying to look at every step is, what is the best insertion point for a city which is not inside my tour again, okay. If you see this one, for instance, it's going to be doing this, right. So when you see this guy, he's probably going to be doing this, this, and that. This guy's going to be doing this and this. And so you basically build your tour starting from, you know a tour of two cities, three cities, four cities and at every point you have a greedy algorithm which insert the next city as best as, you know, you know in the cheapest possible way, okay? So that's to know the greedy algorithm, okay? You going to tell me oh, yeah, yeah but which one I have to use, okay? Well, you know it's not clear which one i have to use on particular input but one of the things that you have noticed here is that these algorithm are easy to actually you know they are, they, they are very fast to run. So you could actually use several of these and take the best solutions. And that's, you know that gives you a particular, you know the first approximation to your particular problem, okay? So, in a sense, summarizing, there are many greedy algorithms that you can conceive, even for something like the traveling salesman problem, and I've only shown you, you know two of them, but there are many more, okay? Some will do better than others on all inputs, or some, you know, will do better on some inputs and not on other ones. OK? It really depends on the partial input, as we have just shown you on one particular instance. Okay? The advantage of greedy algorithm, typically quick to design, quick to implement. You know, they are fast, they typically are fast when you run them. Okay, now the problem is that typically you have no guarantees, you know, the insertion method that I have shown you has guarantee in the case of, you know Euclidean space, okay? But in general you probably don't have any guarantee, okay? So, there are some cases where these greedy algorithms have some guarantees but not always okay, then the quality may vary tremendously depending on different types of input, okay? Once again, you know you don't really know, we can't prove things really. It's a starting point, okay? And of course, we have assumed that it is easy to find a feasible solution. If it is not easy to find a feasable solution, one of the things that you can do is to put some of the constraints inside the objective, and then it is easy to find solution. Then you optimize this function, and try to get as close as possible to a feasible solution, okay? So the the greedy algorithm there would tell you, okay, so this is a solution which is as close as possible to the, you know, to a feasible solution using this greedy algorithm, okay? So, the essence of the class is that you can always start with a greedy algorithm, okay? It gives you a starting point that you can improve afterwards. And then you can look at the techniques that are presented in this class you know constraint programming dynamic programming you know local search and mixed integer programming to try and improve the value its giving you by degree. So really the class is about how to do better than a simple greedy algorithm, okay? But a greedy algorithm is going to give you a certain starting points and you'd starting on this tending what the problem is really about and sometimes these greedy algorithm can be transformed easily okay in constraint programming solutions, okay? There is one step that you can apply and then it moves to a you know particular constraint programming solution, okay? So, you know inside in the class what you learn is finding you know, ways of finding high quality solution. Feasible solution and finding high quality solution which are robust across many inputs. That's what optimization is going to bring to you. And obviously we have techniques where we can actually give you guarantees. You can come back and tell you know and tell you know oh, I have a solution and I know that it's not worse that let's say you know 2% of the optimal value that I could ever find. Okay so in a sense what the class is covering you is how to find you know, you know feasible solution in complex when there are complex constraints. Find high quality solution which are robust across a large spectrum of instances and then give you performance guarantee, quality guarantees on the algorithm that you have, okay? So this is greedy one you know come back to see greedy two. We'll, we'll, we'll go into a little bit more details on how you move from a greedy algorithm to other kinds of techniques, okay? Thank you.