1 00:00:00,320 --> 00:00:03,820 Okay, guys, this is Discrete Optimization Assignments: Getting Started. 2 00:00:03,820 --> 00:00:07,460 So, this is essentially giving you a kind of a philosophical way of how to start 3 00:00:07,460 --> 00:00:11,600 these assignments, if you don't know where to start from. 4 00:00:11,600 --> 00:00:14,470 You get this thing in the face, and you don't know where to start, okay? 5 00:00:14,470 --> 00:00:17,384 That's what we want to address here, okay, and so you can see that you know we 6 00:00:17,384 --> 00:00:21,184 want to, we want to give you some hints on how to get started. 7 00:00:21,184 --> 00:00:24,239 And then we also want to see that in this class there are basically 2 approaches 8 00:00:24,239 --> 00:00:27,294 that you can follow and both of them are rewarded equally, you know because you 9 00:00:27,294 --> 00:00:30,302 get a lot of points when you have a high quality but you'll also get you know 10 00:00:30,302 --> 00:00:35,373 there are also many pause and they are different, okay. 11 00:00:35,373 --> 00:00:38,287 And therefore if you get good great average grade, let's see on everyone of 12 00:00:38,287 --> 00:00:41,622 them that, that can actually bring you up as well, okay? 13 00:00:41,622 --> 00:00:45,840 So, the assignments are intended for modeling, what happens in real life. 14 00:00:45,840 --> 00:00:48,546 You have your boss right? So your big boss coming and saying, you 15 00:00:48,546 --> 00:00:51,550 know, we want you to solve this problem. Okay? 16 00:00:51,550 --> 00:00:53,870 And the boss doesn't care how you're going to do it. 17 00:00:53,870 --> 00:00:55,752 Okay? Just wants results, he just wants to look 18 00:00:55,752 --> 00:00:58,560 good, and the company to be profitable, and so on. 19 00:00:58,560 --> 00:01:00,536 Okay? Think, you know, Kennedy when he decided 20 00:01:00,536 --> 00:01:03,080 here that America needed to go to the moon. 21 00:01:03,080 --> 00:01:05,750 he didn't say, okay so to go to the moon you have to build this rocket. 22 00:01:05,750 --> 00:01:07,552 To build this rocket you have to understand this, and you have to 23 00:01:07,552 --> 00:01:09,952 understand that. And so on, he said, just get me to the 24 00:01:09,952 --> 00:01:12,890 moon, that's what I want. So this is the same thing. 25 00:01:12,890 --> 00:01:14,940 You have your boss, the boss is coming to you. 26 00:01:14,940 --> 00:01:17,705 He's basically telling you, you have to actually solve these problems. 27 00:01:17,705 --> 00:01:20,948 And its actually your responsability, and you don't expect the boss to tell you how 28 00:01:20,948 --> 00:01:23,300 to do this exactly. Right? 29 00:01:23,300 --> 00:01:26,600 But of course we give you a lot of material to actually get there, okay? 30 00:01:26,600 --> 00:01:29,030 It's not like you know nothing about the rockets, right? 31 00:01:29,030 --> 00:01:31,709 So we have given you a variety of techniques, but once again you don't 32 00:01:31,709 --> 00:01:34,670 really know what's going to work or not and I really don't know how, you know, 33 00:01:34,670 --> 00:01:39,178 which one is going to work either. When I see a new problem, for instance, 34 00:01:39,178 --> 00:01:42,640 in that field, that's the, that, that's the nature of the beast. 35 00:01:42,640 --> 00:01:45,590 This is a field where you look at this problem, you say whoo what is going to 36 00:01:45,590 --> 00:01:48,764 work on this, right. And, and so really, you know, one of the 37 00:01:48,764 --> 00:01:53,310 things here is that we're trying to build your intuition your experience, okay. 38 00:01:53,310 --> 00:01:56,062 And so, basically the assignments are like this creativity where you have to 39 00:01:56,062 --> 00:01:59,072 use the various techniques sometimes 2 of them on different parts of the assignment 40 00:01:59,072 --> 00:02:02,200 to get, you know, the result that you want. 41 00:02:02,200 --> 00:02:04,490 Okay? Now one of the big things in optimization 42 00:02:04,490 --> 00:02:08,400 is that when you get a problem, you know, in, in optimization. 43 00:02:08,400 --> 00:02:10,288 Okay? So you have the state of the art, you 44 00:02:10,288 --> 00:02:12,530 know what your company, let's say, is doing. 45 00:02:12,530 --> 00:02:15,292 Okay? So, so let's say they are doing things 46 00:02:15,292 --> 00:02:17,170 manually. You know where they are. 47 00:02:17,170 --> 00:02:20,131 And so the first thing that you do is, you're going to, program something using 48 00:02:20,131 --> 00:02:22,530 optimization. And it's going to give you better results 49 00:02:22,530 --> 00:02:24,200 than what they do in practice. Hopefully. 50 00:02:24,200 --> 00:02:26,120 Okay? And then you can come back to your boss 51 00:02:26,120 --> 00:02:29,650 and say hey boss, you know, I can improve this thing by 20%. 52 00:02:29,650 --> 00:02:31,500 And your boss is going to say, oh that's good. 53 00:02:31,500 --> 00:02:34,821 And he can stop there. And if, if, if, it stops there, it's 54 00:02:34,821 --> 00:02:37,340 fine. You'll have nothing else to do. 55 00:02:37,340 --> 00:02:41,910 Now your boss may be very clever and say, can you actually do better than that? 56 00:02:41,910 --> 00:02:44,560 That's where the problem starts getting interesting. 57 00:02:44,560 --> 00:02:47,632 If your boss is really smart, he's going to say, oh, can you tell me how much you 58 00:02:47,632 --> 00:02:51,290 can improve this? Or, can you actually improve it further? 59 00:02:51,290 --> 00:02:53,455 Okay? And that's where you start looking at 60 00:02:53,455 --> 00:02:56,220 your first solution and try to improve it. 61 00:02:56,220 --> 00:02:59,310 You want to say, oh, can I do a smarter greedy algorithm? 62 00:02:59,310 --> 00:03:02,800 Or, can I use some of the other techniques to actually prove that... 63 00:03:02,800 --> 00:03:06,281 I can't do better or I can only win in another you know .0001% and then you 64 00:03:06,281 --> 00:03:10,175 really don't care, right you can come to your boss and say, yeah you can do better 65 00:03:10,175 --> 00:03:15,265 but probably .0001%. So it's not worthy effort, okay so in a 66 00:03:15,265 --> 00:03:18,923 sense we give you the tool to go beyond the first algorithm and to argue with 67 00:03:18,923 --> 00:03:23,273 your boss in a very intelligent fashion, okay. 68 00:03:23,273 --> 00:03:26,931 So, the baseline, okay, so typically you know, if we have an advice on how to 69 00:03:26,931 --> 00:03:32,390 start you know, look at the problem, start to implement a simple solution. 70 00:03:32,390 --> 00:03:34,540 Okay? A simple Greedy Algorithm. 71 00:03:34,540 --> 00:03:37,576 You know, a simple you know, heuristic for looking at the problem and seeing how 72 00:03:37,576 --> 00:03:41,132 good you are. And then you can take these 2 approaches: 73 00:03:41,132 --> 00:03:44,353 The quality based approach, or let's say the scalability approach. 74 00:03:44,353 --> 00:03:47,233 The scalability approach, the idea is that it's probably going to work on all 75 00:03:47,233 --> 00:03:49,870 of the parts, okay?. It may not be the best on all of the 76 00:03:49,870 --> 00:03:52,200 parts, but it's going to scale naturally, okay? 77 00:03:52,200 --> 00:03:56,230 The quality approach okay, is essentially you know, you will be able to come to 78 00:03:56,230 --> 00:04:01,303 your boss and say, I have the best solution,or I can prove that I. 79 00:04:01,303 --> 00:04:04,506 0.001% of the optimal solution, okay? And there typically you would use 80 00:04:04,506 --> 00:04:06,390 constraint programming or mixed integer programming. 81 00:04:06,390 --> 00:04:09,400 It may not scale to the really large problems, okay? 82 00:04:09,400 --> 00:04:12,050 And some of you have experienced that in graph coloring already. 83 00:04:12,050 --> 00:04:14,571 Okay? And so in a sense these two approaches 84 00:04:14,571 --> 00:04:17,274 are complementary. You can use one of the other in part and 85 00:04:17,274 --> 00:04:20,200 you'll succeed very well in this class. Okay? 86 00:04:20,200 --> 00:04:22,494 Then of course if you're really clever, you can say, hey hey, you know, I can 87 00:04:22,494 --> 00:04:25,572 actually combine these 2. And some of the advanced material in this 88 00:04:25,572 --> 00:04:27,820 class. I'm, telling you how to do that, okay. 89 00:04:27,820 --> 00:04:30,672 So, and that's you know, that's kind of the cherry on the cake, at the end you 90 00:04:30,672 --> 00:04:34,138 can do something like that. Okay, so once again, you can start with 91 00:04:34,138 --> 00:04:36,778 this and then depending upon your standards or you know, where you want to 92 00:04:36,778 --> 00:04:39,374 get in this class you can use one of these 2, and then if you really want to 93 00:04:39,374 --> 00:04:42,102 get to the real top of the leader board you can think about using things like 94 00:04:42,102 --> 00:04:46,050 this. Okay? 95 00:04:46,050 --> 00:04:49,880 So, in a sense you know, one of the things that I will, you know. 96 00:04:49,880 --> 00:04:53,080 You know, keep on telling people is that there is not a single approach that is 97 00:04:53,080 --> 00:04:57,150 going to be successful for every problems in optimization, okay? 98 00:04:57,150 --> 00:05:00,200 And for even, for instances of some of the problem, it's not the case. 99 00:05:00,200 --> 00:05:01,910 You have seen that for the knapsack problem. 100 00:05:01,910 --> 00:05:05,530 You have seen that for, you know, for graph coloring, okay? 101 00:05:05,530 --> 00:05:09,050 So in a sense, the 2 approach that we have here, the scalability and and the 102 00:05:09,050 --> 00:05:13,560 quality approach will give you a way to succeed in this class. 103 00:05:13,560 --> 00:05:15,540 Okay? So, and once again you know I've, you 104 00:05:15,540 --> 00:05:19,460 know, these, these were actually covering the mailbox for the, for the second week, 105 00:05:19,460 --> 00:05:23,100 but the average, the average quality let's say you know if you want a 7 on all 106 00:05:23,100 --> 00:05:27,210 the parts. You can get it let's say from the 107 00:05:27,210 --> 00:05:30,439 scalability approach okay? Or you can get it from a high quality 108 00:05:30,439 --> 00:05:34,570 approach where some of the problems are going to be nicely solved. 109 00:05:34,570 --> 00:05:37,461 Some of them are not going to be but in average you are going to be good, okay so 110 00:05:37,461 --> 00:05:40,548 in a sense and that obviously if you want to really be clever you are going to use 111 00:05:40,548 --> 00:05:43,831 some of these in conjunction with some of the other ones and get essentially 7 and 112 00:05:43,831 --> 00:05:46,624 10 or most of the on most of the assignments, okay so both approach are 113 00:05:46,624 --> 00:05:49,809 viable you can combine them but this is the ID right so you start from [UNKNOWN] 114 00:05:49,809 --> 00:05:52,994 then you take one of these two approaches see how far it gets you and then you can 115 00:05:52,994 --> 00:06:01,440 start combining Okay? now, moving on. 116 00:06:01,440 --> 00:06:03,859 So, it's very important here that you don't get stuck to one particular 117 00:06:03,859 --> 00:06:06,420 assignment. You have this coloring, [INAUDIBLE] you 118 00:06:06,420 --> 00:06:09,165 have 5 types, and then you have these seven, and you are really bothered by 119 00:06:09,165 --> 00:06:12,980 that 7, and you agonize over it. You only think about this. 120 00:06:12,980 --> 00:06:16,230 You know talk to your girlfriend or your boyfriend or your wife or whatever you 121 00:06:16,230 --> 00:06:19,340 just focus on this its obsessed you completely. 122 00:06:19,340 --> 00:06:22,268 Just don't do that, right, so the key idea is that you move on you move to the 123 00:06:22,268 --> 00:06:25,500 next assignment. At some point in the class you may say. 124 00:06:25,500 --> 00:06:28,338 Oh but this technique is really nice I could apply it to that particular problem 125 00:06:28,338 --> 00:06:31,090 you come back to it you solve it in 30 seconds, I'm exaggerating right, but you 126 00:06:31,090 --> 00:06:35,936 solve it and know you're already happy. So don't get stuck to the problem. 127 00:06:35,936 --> 00:06:39,621 move on okay and come back to the problem later you will have the opportunity to do 128 00:06:39,621 --> 00:06:43,136 that., Okay? Now, this is so there is a one week at 129 00:06:43,136 --> 00:06:46,120 the end of the class. If, you know, you have a lot of people 130 00:06:46,120 --> 00:06:48,488 which are just, you know, on the left of this curve, you, you, we will consider 131 00:06:48,488 --> 00:06:52,275 extending, you know, and giving you another week to touch up at the end. 132 00:06:52,275 --> 00:06:54,150 Okay? But we are not in the, we are not in the 133 00:06:54,150 --> 00:06:56,995 position that we need to do that. You know, people are doing well right 134 00:06:56,995 --> 00:06:58,724 now. So, you know, there is just a little bit 135 00:06:58,724 --> 00:07:02,390 push, you know, we just need to push a little bit more people to move. 136 00:07:02,390 --> 00:07:04,610 To move, across the curve. Okay? 137 00:07:04,610 --> 00:07:09,166 Now, this is something, that, you know, I'm always, you know, I, I've always, you 138 00:07:09,166 --> 00:07:14,158 know, mentioned, when, you know, I teach. And I have, you know, most of the class 139 00:07:14,158 --> 00:07:17,528 have big programming assignment. And I always, you know, tell people, this 140 00:07:17,528 --> 00:07:20,990 is not the way you want to do. So, so let me give you an analogy. 141 00:07:20,990 --> 00:07:23,920 So, so Rafael Nadal the great tennis player, right. 142 00:07:23,920 --> 00:07:28,582 So he was basically saying oh yea, when you win a grand slam, you are happy for 143 00:07:28,582 --> 00:07:32,355 15 days. And I was saying, this poor guy is 144 00:07:32,355 --> 00:07:36,840 training the entire year, he spent 15, you know, 50 weeks training, and then he 145 00:07:36,840 --> 00:07:42,740 has these 15 days where he is happy. Wow, that's not a life. 146 00:07:42,740 --> 00:07:45,110 Right? So, and this is the same thing here. 147 00:07:45,110 --> 00:07:47,314 Right? So, you don't want to be unhappy the 148 00:07:47,314 --> 00:07:50,870 entire time and then be ha, happy at the end. 149 00:07:50,870 --> 00:07:54,591 So, what I want, what I don't want you to do is to think about this beautiful 150 00:07:54,591 --> 00:07:57,570 amazingly perfect algorithm. Okay? 151 00:07:57,570 --> 00:07:59,390 And you spec it. Okay? 152 00:07:59,390 --> 00:08:01,320 So, you know what you want and implement. Okay? 153 00:08:01,320 --> 00:08:04,020 And then you start free and then you start implementing, and this is your 154 00:08:04,020 --> 00:08:08,460 degree of happiness or confidence. Is going to decrease, decrease over time 155 00:08:08,460 --> 00:08:11,815 and you become you know more and more happy now you can't see any result you 156 00:08:11,815 --> 00:08:15,170 are coding, coding, coding, coding, coding and then at the end of the, the 157 00:08:15,170 --> 00:08:20,089 assignment period wow! You have a boost you know of happiness 158 00:08:20,089 --> 00:08:23,127 because you just solved the problem, but for all the time here you have been 159 00:08:23,127 --> 00:08:27,726 completely unhappy your confidence has been going, going, going down. 160 00:08:27,726 --> 00:08:30,776 And then you have this rush of blood to the head, for you know 2 weeks or well, 161 00:08:30,776 --> 00:08:34,160 actually in here it's going to be like 1 day right. 162 00:08:34,160 --> 00:08:37,136 So in a sense you don't want that because most of your time is going to be you know 163 00:08:37,136 --> 00:08:40,970 decreasing happiness and then one big rush at the end. 164 00:08:40,970 --> 00:08:45,270 Okay, 1 high period, okay? So this is the way to do it right. 165 00:08:45,270 --> 00:08:49,362 So you start with a reasonable degree of happiness, okay, and then essentially 166 00:08:49,362 --> 00:08:53,330 you'll, you, you start coding and your confidence is going to decrease and then 167 00:08:53,330 --> 00:08:57,321 you know wow! You have a, you know you have a first 168 00:08:57,321 --> 00:09:00,408 high here because you completed the greedy algorithm, it gives you 7 on that 169 00:09:00,408 --> 00:09:03,446 you know a couple of instances so you say oh, okay I feel good you know and I am 170 00:09:03,446 --> 00:09:07,624 just to the beginning of this thing, right? 171 00:09:07,624 --> 00:09:10,786 And then you say oh, you look at this greedy and you say oh, this problem I can 172 00:09:10,786 --> 00:09:14,101 see why it's so bad, and though you start saying oh, this is what I wanted to do, I 173 00:09:14,101 --> 00:09:18,649 want to implement a local search algorithm, okay? 174 00:09:18,649 --> 00:09:21,913 Now, you, happiness decrease a little bit, you could, but then, wow, another 175 00:09:21,913 --> 00:09:24,973 big boost because now you can solve, let's say, 4 or 5, or let's say 6 of the 176 00:09:24,973 --> 00:09:28,607 instances. And so you have a seven on all these 177 00:09:28,607 --> 00:09:31,792 things and you think well I feel pretty good, but you know I would like have some 178 00:09:31,792 --> 00:09:33,510 10. Okay? 179 00:09:33,510 --> 00:09:36,646 And then now you start, you know using MIP, you know, let's say a MIP approach, 180 00:09:36,646 --> 00:09:39,782 okay, and once again, you know, your, your happiness and your confidence are 181 00:09:39,782 --> 00:09:44,014 going to decrease. But then wow another big high because you 182 00:09:44,014 --> 00:09:47,900 are basically, you know completed that assignment. 183 00:09:47,900 --> 00:09:50,378 It may work or it may not work but at this point you say wow, at least I have 184 00:09:50,378 --> 00:09:54,235 something and I can talk about it, okay. And then afterwards you say oh, but you 185 00:09:54,235 --> 00:09:56,965 know really I should have used CP on this thing, you know, you start coding this 186 00:09:56,965 --> 00:09:59,653 thing you know once again your happiness you know decreases but then you have 187 00:09:59,653 --> 00:10:02,383 another big rush at the end because you completed all the approach and then you 188 00:10:02,383 --> 00:10:06,467 have a 10 on everyone of these assignment. 189 00:10:06,467 --> 00:10:09,897 That's what we want you to do, okay? [INAUDIBLE] one part, you know, get a 190 00:10:09,897 --> 00:10:13,110 high for a couple of days, you know, then basically go down and, you know, get 191 00:10:13,110 --> 00:10:17,438 another solution and so on. So, the average happiness here is much 192 00:10:17,438 --> 00:10:22,020 higher than in the previous curve, okay, and you are basically stable, right. 193 00:10:22,020 --> 00:10:25,216 It's not like a decreasing curve. Where your happiness is always 194 00:10:25,216 --> 00:10:28,912 decreasing, decreasing, okay, so this is what we what you to do in a sense, okay, 195 00:10:28,912 --> 00:10:32,417 so try to put these thinks in, you know, in a bottom of fashion in an agile way 196 00:10:32,417 --> 00:10:35,968 [UNKNOWN] results early you are not getting depressed you don't try to build 197 00:10:35,968 --> 00:10:42,504 this thing in one big stack, okay. So this is basically the advice that we 198 00:10:42,504 --> 00:10:45,640 have for you, you know, try to have fun during the journey otherwise it's like 199 00:10:45,640 --> 00:10:48,727 you know, spending 15 weeks, 50 weeks just training and then getting these 2 200 00:10:48,727 --> 00:10:53,714 weeks where you're happy. We want you to be happy 50 weeks and then 201 00:10:53,714 --> 00:10:57,520 have these 2 you know, weeks period where you work really hard. 202 00:10:57,520 --> 00:10:58,960 Okay? Great, thank you guys.