1 00:00:00,008 --> 00:00:03,000 Okay? So what we are going to do here is to 2 00:00:03,000 --> 00:00:08,480 look at some optimization tools and some kind of philosophy of what you can use 3 00:00:08,480 --> 00:00:11,160 inside of the class. So for the various assignments. 4 00:00:11,160 --> 00:00:13,790 So we give you a lot of freedom, right? So you can do whatever you want. 5 00:00:13,790 --> 00:00:17,630 You can, you know start coding everything in assembly if you want. 6 00:00:17,630 --> 00:00:20,442 You can code in ruby if you are interested in that. 7 00:00:20,442 --> 00:00:24,100 You, you, you can do whatever you want. You can even use, you know general 8 00:00:24,100 --> 00:00:28,300 purpose optimization tools if you want. And it may be a good idea in, in some of 9 00:00:28,300 --> 00:00:30,730 these assignments, okay? So you don't need to reinvent the wheel. 10 00:00:30,730 --> 00:00:34,040 You can if you want, okay? So once again this class is about giving 11 00:00:34,040 --> 00:00:35,740 you as much freedom as you can. Okay? 12 00:00:35,740 --> 00:00:38,880 So if you use a general optimization tools there will be a number of 13 00:00:38,880 --> 00:00:40,950 advantages. They are generally very, you know 14 00:00:40,950 --> 00:00:43,555 designed so that you can very quickly design these model. 15 00:00:43,555 --> 00:00:45,890 Okay? And get a quick solution. 16 00:00:45,890 --> 00:00:50,860 They are going to be generally, you know efficient in, in the kinds of, of 17 00:00:50,860 --> 00:00:53,800 technology that they are implementing. That doesn't mean that your model is 18 00:00:53,800 --> 00:00:56,130 going to run fast because your model may be terrible, okay? 19 00:00:56,130 --> 00:00:59,320 Or the problem is so hard that, you know no model is very good. 20 00:00:59,320 --> 00:01:01,220 Okay? But typically these tools include, you 21 00:01:01,220 --> 00:01:06,365 know years of, years of research. And, you know they spend a lot of time 22 00:01:06,365 --> 00:01:08,630 optimizing the algorithm that they're providing, okay? 23 00:01:08,630 --> 00:01:12,930 Now in, in, in, the disadvantage of using these tools is that you will have to 24 00:01:12,930 --> 00:01:16,020 learn them and sometimes learning them is not so easy, okay? 25 00:01:16,020 --> 00:01:20,970 there may be limitation of what they are allowing you to do and how you can extend 26 00:01:20,970 --> 00:01:24,610 them if you need to have, you know more capabilities. 27 00:01:24,610 --> 00:01:28,810 They are always slower than, you know a dedicated algorithm if you would spend 28 00:01:28,810 --> 00:01:31,690 just the same amount of energy to solve a particular problem. 29 00:01:31,690 --> 00:01:33,520 Okay? Now in practice that may not be cost 30 00:01:33,520 --> 00:01:35,740 effective, right? So you developing the same kind of 31 00:01:35,740 --> 00:01:39,390 quality as the system would take you much longer than just using them. 32 00:01:39,390 --> 00:01:42,912 But you, know you can also find a way to do better, okay? 33 00:01:42,912 --> 00:01:47,071 you know just recording some of these stuff and specialize in them for 34 00:01:47,071 --> 00:01:47,985 instance. Okay? 35 00:01:47,985 --> 00:01:52,850 but, but this is a trader that you need to deal with and then they may sometimes 36 00:01:52,850 --> 00:01:53,984 appear to do strange things. Most of the systems these days are using 37 00:01:53,984 --> 00:01:55,510 randomization. They may not even give you the same 38 00:01:55,510 --> 00:02:00,570 solution, you know if you run them twice in a raw. 39 00:02:00,570 --> 00:02:04,720 So and it's always they will do all kinds of transformations as well. 40 00:02:04,720 --> 00:02:08,070 So it may be that you have a good formulation or bad formulation you won't 41 00:02:08,070 --> 00:02:11,620 see a difference because this system are clever enough to actually reformulate the 42 00:02:11,620 --> 00:02:13,880 problem. They recognize that, you know you had a 43 00:02:13,880 --> 00:02:17,580 bad molar and they can reformulate it. So these things, you know there are a lot 44 00:02:17,580 --> 00:02:20,370 of things that you need to take into account when you use various tools. 45 00:02:20,370 --> 00:02:22,755 Okay? So the type of tools that you can use are 46 00:02:22,755 --> 00:02:26,095 CP solvers, MIP solvers, Roco solvers. There are many of them. 47 00:02:26,095 --> 00:02:28,840 Okay? So one of the things that in this class 48 00:02:28,840 --> 00:02:32,400 we won't do is recommend a particular, you know set of tools. 49 00:02:32,400 --> 00:02:34,710 We give you a list. You can choose from that list for 50 00:02:34,710 --> 00:02:37,180 instance. There are other solvers that are not 51 00:02:37,180 --> 00:02:39,940 mentioned int he list. We are not trying to be exhaustive.Okay. 52 00:02:39,940 --> 00:02:43,300 Some of them are open source. You can use them, you know you can use 53 00:02:43,300 --> 00:02:46,470 them, look at the code if you want. Some of them are free for non-commercial 54 00:02:46,470 --> 00:02:47,530 use. Okay. 55 00:02:47,530 --> 00:02:49,650 Some of them are free for students. Okay? 56 00:02:49,650 --> 00:02:52,940 So, so once again, you know for some of them you will need an account in a 57 00:02:52,940 --> 00:02:55,200 university to be able to solve them. Okay? 58 00:02:55,200 --> 00:02:58,730 So you have to find the right tools for the right circumstances in which you are 59 00:02:58,730 --> 00:03:01,430 working on, working on. But there are a lot of tools that are 60 00:03:01,430 --> 00:03:03,227 available and you have to take them into account. 61 00:03:03,227 --> 00:03:07,020 Okay? So so, let, let, you know let, let me 62 00:03:07,020 --> 00:03:10,320 give you an example of the kind of stuff that you, you want to see. 63 00:03:10,320 --> 00:03:14,424 You, you may want to try out and, and then you will want to see the soluable 64 00:03:14,424 --> 00:03:17,356 supporting things like this. So this is a very, you know the Queens 65 00:03:17,356 --> 00:03:20,460 example that we saw many times. And you have a lot of these binary 66 00:03:20,460 --> 00:03:25,490 constraints, inequalities, dis-equalities between the various the various 67 00:03:25,490 --> 00:03:26,650 variables. Okay? 68 00:03:26,650 --> 00:03:29,340 You may say ooh, but this is like all different so I can read. 69 00:03:29,340 --> 00:03:32,000 We formulate as a set of different constraints. 70 00:03:32,000 --> 00:03:34,930 And maybe you know your system is going to support these two formulations 71 00:03:34,930 --> 00:03:35,940 or maybe not. Okay? 72 00:03:35,940 --> 00:03:39,495 So but, but you may try these two models and see how they behave. 73 00:03:39,495 --> 00:03:43,784 Okay? So in a sense if your solver, you know if 74 00:03:43,784 --> 00:03:46,360 your solver doesn't support this. Okay? 75 00:03:46,360 --> 00:03:49,970 Then you may decide to recode, you know all different yourself. 76 00:03:49,970 --> 00:03:52,934 This is what I mentioned there. Or you can say, you can look for a CP 77 00:03:52,934 --> 00:03:55,643 solver which is actually, you know supporting all different, most of the CP 78 00:03:55,643 --> 00:03:58,335 solvers these days would. Okay? 79 00:03:58,335 --> 00:04:06,349 so so let me give you an example of the second option here. 80 00:04:06,349 --> 00:04:10,369 So this is, you know the N-Queens problem in the Comet programming languages and 81 00:04:10,369 --> 00:04:13,429 system, okay? So this is the first model, it's very 82 00:04:13,429 --> 00:04:16,531 close to the kinds of models that we have used inside the slides, so you can stick 83 00:04:16,531 --> 00:04:19,870 that model that way. If you want to change it to the old 84 00:04:19,870 --> 00:04:22,600 different formulation you just remove these constraints and replace them by 85 00:04:22,600 --> 00:04:25,795 those and you can test these two models. Okay? 86 00:04:25,795 --> 00:04:28,391 So what this is showing you is a different, you know different, you know 87 00:04:28,391 --> 00:04:31,515 different tools with actually a different functionalists but they will allow you to 88 00:04:31,515 --> 00:04:35,600 very rapidly prototype different types of solutions. 89 00:04:35,600 --> 00:04:38,870 Okay? so when you see the little box, okay? 90 00:04:38,870 --> 00:04:44,079 Most of the assignments they are typically implemented using dedicated 91 00:04:44,079 --> 00:04:47,025 algorithms, they are not using you know black box solvers in general. 92 00:04:47,025 --> 00:04:51,550 but you know that doesn't mean that, you know you can get close to the solution 93 00:04:51,550 --> 00:04:56,150 using, you know general purpose solvers in general, you can. 94 00:04:56,150 --> 00:04:59,110 Okay? we don't recommend any solver technology 95 00:04:59,110 --> 00:05:00,780 in the class as I told you before. Okay? 96 00:05:00,780 --> 00:05:04,240 So we don't, you know we, so one of the, one of the things that this class is 97 00:05:04,240 --> 00:05:07,210 trying to communicate to you is that different problems will be amenable to 98 00:05:07,210 --> 00:05:09,850 different types of solutions. And some of them may be more appropriate 99 00:05:09,850 --> 00:05:14,620 for different kinds of problems, okay? So, so you can try all the various 100 00:05:14,620 --> 00:05:16,740 technology and all the various solvers that you want. 101 00:05:16,740 --> 00:05:19,170 And all the different techniques. Or you can implement all the various 102 00:05:19,170 --> 00:05:22,172 techniques on every one of the problems. Okay? 103 00:05:22,172 --> 00:05:28,040 we want, when, when the class is running, we want basically to answer, you know 104 00:05:28,040 --> 00:05:32,070 specific questions on all the solvers. At first we don't know them all, okay? 105 00:05:32,070 --> 00:05:36,330 And then, you know this is something that for you actually to figure out, okay? 106 00:05:36,330 --> 00:05:39,555 I've used the insider forum and so on you can ask question you can get 107 00:05:39,555 --> 00:05:44,130 reccomendation from your friends and so on and that's completely fine. 108 00:05:44,130 --> 00:05:48,430 Just don't except us to actually answer questions on dedicated solvers and what 109 00:05:48,430 --> 00:05:51,080 they do and why do they certain things and so on. 110 00:05:51,080 --> 00:05:55,180 Because that would kind of a exponentially many variables to optimize 111 00:05:55,180 --> 00:05:58,390 with many constraints, okay? So thank you very much.