1 00:00:00,060 --> 00:00:02,730 Sample is called the conference allocation. 2 00:00:03,210 --> 00:00:11,280 Suppose we have we are about to organize a conference and um, for example, let's say the participants 3 00:00:11,280 --> 00:00:19,350 are participating in this event from, let's say, 20, uh, different cities or countries. 4 00:00:20,270 --> 00:00:29,810 And, um, but unfortunately, due to some restrictions, they can't all travel to one location to have 5 00:00:29,810 --> 00:00:36,890 the conference right there and they don't have the, um, communication facilities at every city. 6 00:00:36,940 --> 00:00:47,930 OK, so, um, the question is, is it possible to, um, pick up some specific cities and then connect 7 00:00:47,930 --> 00:00:50,280 these cities with a teleconference to each other? 8 00:00:50,520 --> 00:01:00,140 OK, so the question is, how can we, um, choose and some a specific number of cities for having the 9 00:01:00,140 --> 00:01:06,020 teleconference facilities right there and then connect them together in a way that the traveling costs 10 00:01:06,020 --> 00:01:07,460 are minimized? 11 00:01:07,610 --> 00:01:13,390 OK, so, uh, let's solve the problem together. 12 00:01:13,450 --> 00:01:21,210 OK, so we want to minimize the, um, traveling time and traveling distances. 13 00:01:21,230 --> 00:01:25,930 OK, so let's define a binary variable like l iji. 14 00:01:26,210 --> 00:01:31,070 It means that the travel should happen between IFJ. 15 00:01:32,090 --> 00:01:40,550 And multiply it by the distance between these two cities and also, um, there are some other constraints. 16 00:01:40,550 --> 00:01:49,130 For example, this one, the summation of Elijah over Jay means that every person living in a city I 17 00:01:49,460 --> 00:01:51,770 should only travel to one city. 18 00:01:52,040 --> 00:01:54,760 OK, so not more than that. 19 00:01:55,760 --> 00:02:01,460 And also the number of chosen cities are already specified. 20 00:02:01,460 --> 00:02:06,800 Let's call and see the sort of summation of UI, which is a binary variable as well. 21 00:02:07,100 --> 00:02:09,910 And over I will be and see. 22 00:02:10,340 --> 00:02:22,400 And finally, um, let's say UI is telling us if a city is chosen for having the teleconference facilities 23 00:02:22,400 --> 00:02:30,190 or not, then, um, another consideration should be, uh, written here. 24 00:02:30,200 --> 00:02:34,780 Let's say Ellijay should be less than equal to a UI plus Euge. 25 00:02:35,510 --> 00:02:36,510 What does it mean? 26 00:02:36,530 --> 00:02:43,220 It means that if a traveler is going to happen between I and J, then, um. 27 00:02:44,470 --> 00:02:49,120 At least one of them should have the teleconference facilities, OK? 28 00:02:49,570 --> 00:02:55,900 It can't be the case that if none of these cities have, uh, teleconference facilities and traveling 29 00:02:55,900 --> 00:02:57,520 is happening, for example. 30 00:02:58,000 --> 00:03:06,670 And here you can see that for 20, uh, cities, city number five, city number one and number 10 are 31 00:03:06,670 --> 00:03:09,850 chosen to host the teleconference. 32 00:03:11,110 --> 00:03:17,180 But, um, there is no travel happening between 11 and 16, for example. 33 00:03:17,470 --> 00:03:21,360 OK, OK, so and this is it. 34 00:03:22,180 --> 00:03:26,950 If I have, let me show you some sensitivity analysis. 35 00:03:27,320 --> 00:03:32,170 So, uh, suppose we have, uh, the same number of cities, 20. 36 00:03:32,390 --> 00:03:32,690 Mm. 37 00:03:33,010 --> 00:03:37,900 So all of them are, um, scattered on the plane the same way. 38 00:03:38,170 --> 00:03:44,360 But each case, the number of conference facilities are changed. 39 00:03:44,380 --> 00:03:48,380 So first of all, only two cities are, uh, chosen. 40 00:03:48,700 --> 00:03:49,670 You can see it here. 41 00:03:50,020 --> 00:03:52,980 So the objective function is one point six three five. 42 00:03:53,470 --> 00:04:00,520 If I increase the number of cities equal to, let's say, four, so the objective function will even 43 00:04:00,970 --> 00:04:01,630 reduce. 44 00:04:02,890 --> 00:04:10,510 And if I increase the number again by six, then it means that the objective function is now lower. 45 00:04:11,020 --> 00:04:17,430 And finally, if I choose eight points, then the objective function is at minimum. 46 00:04:17,620 --> 00:04:27,430 So you can see that if we have 20 cities and if it is possible to choose all of them to have teleconference 47 00:04:27,430 --> 00:04:34,420 facilities, then the objective function will become zero because no traveling is going to happen. 48 00:04:34,720 --> 00:04:45,700 OK, so, uh, just, uh, have another look at the, um, uh, formulation and I will, uh, run the 49 00:04:46,360 --> 00:04:48,220 Python code for you. 50 00:04:49,210 --> 00:04:53,080 So here you can see that, uh. 51 00:04:54,110 --> 00:04:55,670 And this is the Python code. 52 00:04:56,630 --> 00:05:06,140 So first of all, I import every required, um, well, packages, then, um, we have to write down 53 00:05:06,140 --> 00:05:09,200 the, um, required constraints. 54 00:05:09,200 --> 00:05:13,180 So and is the number of cities and the number of conference to be allocated. 55 00:05:13,580 --> 00:05:15,650 I enjoy representing the nodes. 56 00:05:15,650 --> 00:05:23,360 Um, you is the buyer valuable showing that if a city I is chosen for having the telecoms facilities 57 00:05:23,360 --> 00:05:23,780 or not. 58 00:05:23,990 --> 00:05:30,530 The link is telling that uh, if I are connected to each other, it's a binary variable as well as objective 59 00:05:30,530 --> 00:05:33,170 function is also defined. 60 00:05:33,170 --> 00:05:36,710 Um, the locations of the loans are randomly generated. 61 00:05:38,230 --> 00:05:49,990 And also so I want to write down the codes so the summation of UI or AI is equal to NC and also a summation 62 00:05:49,990 --> 00:05:54,550 of a link I j the submission of a J should be one. 63 00:05:54,800 --> 00:05:57,940 You should keep in mind that J should be different with AI. 64 00:05:58,570 --> 00:06:02,770 And also this one is telling us, um. 65 00:06:03,760 --> 00:06:10,500 Modelling age should be less than UI plus huge if I are different than each other. 66 00:06:11,660 --> 00:06:19,080 And finally, that's the objective function, objective function is defined this way, so, um, I didn't 67 00:06:19,220 --> 00:06:24,400 define a new parameter d to to, um, to be calculated. 68 00:06:24,410 --> 00:06:27,170 I just wrote that expression here. 69 00:06:27,250 --> 00:06:33,920 OK, so you can easily see that how the objective function is defined, multiplied by digit, which 70 00:06:33,920 --> 00:06:35,210 is an expression like this. 71 00:06:35,720 --> 00:06:47,780 And the solver is chosen to be um glyptic and the number of cities are 20 and trees, uh, conference 72 00:06:47,780 --> 00:06:50,600 centers are considered for this purpose. 73 00:06:51,260 --> 00:06:55,130 The model will be created using D-line. 74 00:06:55,190 --> 00:07:00,980 It means that all the constraints and the associated input data will be fed into the model. 75 00:07:01,370 --> 00:07:09,830 And then, um, this is the chosen solver will solve that, uh, create model. 76 00:07:09,830 --> 00:07:13,610 And the objective function is, uh, given to you. 77 00:07:13,820 --> 00:07:23,510 OK, and, um, this case is solved for 20 cities and three conference centers, but you can easily, 78 00:07:23,510 --> 00:07:32,090 uh, create a loop to change those, um, ency centers and see what is the impact. 79 00:07:32,450 --> 00:07:32,650 Hmm. 80 00:07:33,050 --> 00:07:40,820 So I run the code again for you since the code is written in a way that every time it is run, um, 81 00:07:42,020 --> 00:07:44,400 the locations of the. 82 00:07:45,320 --> 00:07:53,600 Cities are changed and updated in a random way, so the objective functions are different in every case, 83 00:07:53,600 --> 00:07:59,960 but you can see that by increasing the number of cities, the objective function is reducing, you know, 84 00:08:00,140 --> 00:08:01,760 see, OK. 85 00:08:02,970 --> 00:08:10,400 And also, sometimes you want to know what's going on inside one of those equations, for example, 86 00:08:10,800 --> 00:08:12,240 let me show you one of them. 87 00:08:12,240 --> 00:08:14,620 For example, equation two here. 88 00:08:15,240 --> 00:08:24,210 So it is doing what it is, um, trying to do the summation l i j link. 89 00:08:24,240 --> 00:08:25,440 I'm doing this. 90 00:08:25,500 --> 00:08:27,210 Much of it should be equal to. 91 00:08:28,870 --> 00:08:36,160 One, it means that the outgoing, um, the travel between each node should be exactly one, not more 92 00:08:36,160 --> 00:08:36,490 than that. 93 00:08:36,790 --> 00:08:48,220 So here you can see at the end for, um, if the starting point is one, then one plus two plus one 94 00:08:48,220 --> 00:08:53,280 plus three one four one five one six one seven to the end. 95 00:08:53,290 --> 00:09:01,570 OK, though that that should be equal to one and you can see was exactly happening inside each constraint. 96 00:09:01,570 --> 00:09:08,230 I just put the equation number two, but you can change the name of the equation and specify any other 97 00:09:08,230 --> 00:09:09,290 equation that you want. 98 00:09:09,970 --> 00:09:19,360 This is definitely useful for doing the debugging and finding out, um, where exactly you might have, 99 00:09:19,690 --> 00:09:23,170 uh, wrongly coded your, um, constraints. 100 00:09:23,380 --> 00:09:25,180 OK, thank you very much.