1 00:00:00,150 --> 00:00:02,704 So welcome back. This is Discrete Optimization Constraint 2 00:00:02,704 --> 00:00:05,036 Programming, and this is part seven. Okay. 3 00:00:05,036 --> 00:00:07,997 So I'm very excited about this lecture, because it's still about redundant 4 00:00:07,997 --> 00:00:11,123 constraints. But it's going to be about one of the 5 00:00:11,123 --> 00:00:14,112 first beautiful model that I wrote [INAUDIBLE] and I'll will tell you the 6 00:00:14,112 --> 00:00:16,508 story later on. Okay. 7 00:00:16,508 --> 00:00:19,118 But, we are still in redundant constraints and expressing how you can 8 00:00:19,118 --> 00:00:23,040 actually put these new constraints that we put in search space much more. 9 00:00:23,040 --> 00:00:24,941 Okay. So, this is actually a real example that 10 00:00:24,941 --> 00:00:27,730 I'm going to talk about. It's about car sequencing. 11 00:00:27,730 --> 00:00:29,655 Okay. So, what you see there is an assembly 12 00:00:29,655 --> 00:00:32,404 line for cars. And you have to understand how this 13 00:00:32,404 --> 00:00:34,350 works. So, in practice, you know, when you 14 00:00:34,350 --> 00:00:37,600 produce these cars, the object of this assembly line that is moving in front of 15 00:00:37,600 --> 00:00:39,802 production unit. Okay. 16 00:00:39,802 --> 00:00:43,150 So, these production units are responsible for actually putting options 17 00:00:43,150 --> 00:00:46,336 on the car. And an option can be, you know, leather 18 00:00:46,336 --> 00:00:49,258 seats or moon roof. But on production, you need to have to go 19 00:00:49,258 --> 00:00:51,420 fast, because essentially the, the cars are moving. 20 00:00:51,420 --> 00:00:54,703 And so they have a capacity constraint, which is essentially telling, telling, 21 00:00:54,703 --> 00:00:57,888 you know, the, the, the people assembling the line, how many options they, how 22 00:00:57,888 --> 00:01:02,346 many, on how many cars they can put this option in a row, okay. 23 00:01:02,346 --> 00:01:05,286 So, for instance, they may have a constraint that tells you, you know, at 24 00:01:05,286 --> 00:01:08,471 most two of the five successive cars you know, can require a moon roof, because 25 00:01:08,471 --> 00:01:13,520 otherwise the production unit won't have the time to actually put it on. 26 00:01:13,520 --> 00:01:15,262 Okay. So, essentially what you have is a huge 27 00:01:15,262 --> 00:01:17,798 amount of cars that you have to produce. Okay. 28 00:01:17,798 --> 00:01:19,848 Specifically in the number of hundreds. Okay. 29 00:01:19,848 --> 00:01:22,910 And you have these capacity constraints on the production unit. 30 00:01:22,910 --> 00:01:25,835 These different cars have different configurations of the various options, 31 00:01:25,835 --> 00:01:28,625 and you have to sequence them such that all these capacity constraints are 32 00:01:28,625 --> 00:01:31,700 satisfied. So let me show you an example. 33 00:01:31,700 --> 00:01:35,154 This is an example of, this is an instance of that problem, okay. 34 00:01:35,154 --> 00:01:38,281 So what you saw here on top of the various configurations of car that you 35 00:01:38,281 --> 00:01:41,673 need to produce, you know, every time that you see a yellow, that means this is 36 00:01:41,673 --> 00:01:46,786 a popular option, which is required. So you can assume that the first option 37 00:01:46,786 --> 00:01:51,150 there is a moon roof, the second one is a letter C, then so on and so forth. 38 00:01:51,150 --> 00:01:53,651 The tiny numbers that you see there, it's not important what they are, but 39 00:01:53,651 --> 00:01:58,240 [INAUDIBLE] basically the number of cars requiring that particular configuration. 40 00:01:58,240 --> 00:02:00,482 What you see at the bottom is very interesting, okay. 41 00:02:00,482 --> 00:02:03,315 So that's the assembly line, okay. So the capacity that you see there are 42 00:02:03,315 --> 00:02:06,040 the capacity of the various production units. 43 00:02:06,040 --> 00:02:09,144 The first one there is one out of two. That basically means that every other car 44 00:02:09,144 --> 00:02:11,993 cannot require that option. You wouldn't have the time to all, to be, 45 00:02:11,993 --> 00:02:13,038 put it on. Okay. 46 00:02:13,038 --> 00:02:16,419 The next one is one out of three that means out of three successive cars, well 47 00:02:16,419 --> 00:02:20,639 it's actually two out of three. Of the three successive cars at most two 48 00:02:20,639 --> 00:02:24,000 can take the option. And the last one is one out of five. 49 00:02:24,000 --> 00:02:25,903 Okay. So, if you take five successive slot, at 50 00:02:25,903 --> 00:02:29,150 most one car can actually be scheduled there. 51 00:02:29,150 --> 00:02:32,384 So, for every one of these constraints, this is actually the legal sequencing, 52 00:02:32,384 --> 00:02:35,922 you know, of, of all the cars. If you, you know, if for the first row, 53 00:02:35,922 --> 00:02:38,937 if you take, say like, you know two, two two successive slots, only one of them 54 00:02:38,937 --> 00:02:42,750 will be yellow. For the last one, if you take any kind of 55 00:02:42,750 --> 00:02:46,050 five successive slots, a window of five successive slots, they will be only one 56 00:02:46,050 --> 00:02:49,394 car required, requesting that option. Okay. 57 00:02:49,394 --> 00:02:52,444 So your goal is to take all these things at the top and produce what is at the 58 00:02:52,444 --> 00:02:55,794 bottom, and make sure that every one of these capacity restraints is accurately 59 00:02:55,794 --> 00:02:59,350 satisfied. Okay, so how do we do that? 60 00:02:59,350 --> 00:03:02,298 This is a simple example that I will use for illustrating some of the propagation 61 00:03:02,298 --> 00:03:06,798 and some of the probabilities at the end. So it's good to familiarize yourself a 62 00:03:06,798 --> 00:03:09,934 little bit with it, so what you see there are the various classes of car that we 63 00:03:09,934 --> 00:03:13,327 have to produce on top of the options. Okay. 64 00:03:13,327 --> 00:03:16,462 So this is class one, class one is going to require option one, option 65 00:03:16,462 --> 00:03:20,843 three, and option four, okay. And the demand for that particular car is 66 00:03:20,843 --> 00:03:25,010 one, so the last one that you see there, this is class six. 67 00:03:25,010 --> 00:03:27,404 Okay. It requires option one, option two, and 68 00:03:27,404 --> 00:03:30,750 you need to produce two cars of that type. 69 00:03:30,750 --> 00:03:32,732 Okay. Now these are the production unit for 70 00:03:32,732 --> 00:03:36,582 everyone of the, of the option. Okay, so look at this option here, this 71 00:03:36,582 --> 00:03:40,852 is option five this is one over five. Once again window of five slots and only 72 00:03:40,852 --> 00:03:44,202 one car of the type. Okay, so that's the example I will use 73 00:03:44,202 --> 00:03:45,474 later on. Okay. 74 00:03:45,474 --> 00:03:48,850 So this is the model okay, it's a beautiful model. 75 00:03:48,850 --> 00:03:51,430 so what you have there is first a set of data. 76 00:03:51,430 --> 00:03:54,870 You have the slots that's basically you know, all the slots of the assembly line. 77 00:03:54,870 --> 00:03:57,540 You have the various configuration that you see on the top. 78 00:03:57,540 --> 00:04:00,109 That's the, the, the type of car that you have to produce. 79 00:04:00,109 --> 00:04:03,740 The various options you know, moon, moon roof, you know, leather seats and so on. 80 00:04:03,740 --> 00:04:06,485 The demand for every one of these configuration, that's how many cars you 81 00:04:06,485 --> 00:04:09,044 have to produce. You have a lower bound and an upper bound 82 00:04:09,044 --> 00:04:11,945 for every one of the options, you know. Lower bound means when you have a 83 00:04:11,945 --> 00:04:14,415 constraint two out of five, the lower bound would be two, the upper bound would 84 00:04:14,415 --> 00:04:18,100 be five. Now, the interesting decision variables 85 00:04:18,100 --> 00:04:21,178 here are the line variables so that essentially for every slot of the 86 00:04:21,178 --> 00:04:25,239 assembly line, okay. That decision variable will tell you what 87 00:04:25,239 --> 00:04:28,044 type of car you have to produce there, okay. 88 00:04:28,044 --> 00:04:33,270 Now, we use a set of auxiliary variables here, which are the setup variable and 89 00:04:33,270 --> 00:04:37,388 Set up all S when essentially its going to be one when option S is required 90 00:04:37,388 --> 00:04:42,870 on slot S of the assembly line. So that basically mean that the sla, the, 91 00:04:42,870 --> 00:04:46,493 the car which the, the type of car which is scheduled on slot as S to re, requires 92 00:04:46,493 --> 00:04:49,216 [INAUDIBLE] option. Okay. 93 00:04:49,216 --> 00:04:52,696 Now we strictly don't need these variables but they make it easy to state 94 00:04:52,696 --> 00:04:54,709 the constraints. Okay. 95 00:04:54,709 --> 00:04:57,934 So then you see the constraints. The first one is the capacity constraints 96 00:04:57,934 --> 00:04:59,989 that you're going to see there. Okay. 97 00:04:59,989 --> 00:05:03,260 The demand constraints. And that particular constraints is 98 00:05:03,260 --> 00:05:05,906 basically telling you, well if you have a particular type of car, you have to 99 00:05:05,906 --> 00:05:08,620 produce enough car of that particular type. 100 00:05:08,620 --> 00:05:10,616 Okay. So, and the way you do it is exactly as 101 00:05:10,616 --> 00:05:14,716 in the magic series example. Okay so you basically count the number of 102 00:05:14,716 --> 00:05:17,950 all currencies of that type, that type of car in the line, and the summation is to 103 00:05:17,950 --> 00:05:22,220 be equal to the demand of that type of car. 104 00:05:22,220 --> 00:05:25,124 The next constraint is very easy, okay, what it deci, what it basically defines 105 00:05:25,124 --> 00:05:28,390 are the set of variables that I talked about before, okay? 106 00:05:28,390 --> 00:05:32,660 So set up of OS is going to be equal to the value of requires, which is part of 107 00:05:32,660 --> 00:05:36,892 the data, okay. Of all and the, and the type of car which 108 00:05:36,892 --> 00:05:40,330 is scheduled in slot S of the assembly line. 109 00:05:40,330 --> 00:05:41,990 So in a sense, that's the decision variable. 110 00:05:41,990 --> 00:05:44,491 Once we know the value in a sense, we'll know what type of car and then we can 111 00:05:44,491 --> 00:05:47,880 compute the set of variables for that part of the car. 112 00:05:47,880 --> 00:05:51,156 And then the last constraint is basically the capacity constraints for the 113 00:05:51,156 --> 00:05:53,956 production unit. I won't go into the detail, but 114 00:05:53,956 --> 00:05:57,284 essentially what you do is you take this time windows, okay, of you know upper 115 00:05:57,284 --> 00:06:00,532 bound slot. That's why you see the upper bounds 116 00:06:00,532 --> 00:06:03,521 somewhere here. Okay, and then what you want to make sure 117 00:06:03,521 --> 00:06:07,340 is that at most, the lower bounds, you know they, they are at most the number of 118 00:06:07,340 --> 00:06:13,490 low, the, the value of the lower bound cars that you produce of that type. 119 00:06:13,490 --> 00:06:15,760 And that's what these constraints is basically expressing. 120 00:06:15,760 --> 00:06:17,600 Okay. So you took the set of variable, you 121 00:06:17,600 --> 00:06:20,894 summed them for windows of five and that is to be small or equal to the lower 122 00:06:20,894 --> 00:06:24,174 bound. You know two out of five, at most two out 123 00:06:24,174 --> 00:06:25,944 of five. You would make sure that this is smaller 124 00:06:25,944 --> 00:06:26,756 than two. Okay. 125 00:06:26,756 --> 00:06:28,650 So that's the motor. Okay. 126 00:06:28,650 --> 00:06:31,450 So it use a lot of the feature of constraint programming. 127 00:06:31,450 --> 00:06:34,555 Refine constraints, element constraints, and then the sums over there. 128 00:06:34,555 --> 00:06:37,980 Okay, and so this is a little bit of the system is working right. 129 00:06:37,980 --> 00:06:41,870 So you see as soon as you place accounts, this is type one, okay. 130 00:06:41,870 --> 00:06:46,090 So you know that since the demand is one you will only produce one of these type. 131 00:06:46,090 --> 00:06:50,170 And of course there is no other car. That can be scheduled on that slot, okay. 132 00:06:50,170 --> 00:06:53,370 Now what is interesting to see is what is happening to the option, okay. 133 00:06:53,370 --> 00:06:57,335 So you know that class one over there okay, is requesting option one, three and 134 00:06:57,335 --> 00:07:00,704 four, okay. And that's what you see there, right, the 135 00:07:00,704 --> 00:07:04,172 blue stuff is basically telling you that the car, you know, that slot is requiring 136 00:07:04,172 --> 00:07:07,060 option one, three and four. Okay. 137 00:07:07,060 --> 00:07:10,120 And then what you see which is interesting is already the propagation of 138 00:07:10,120 --> 00:07:13,710 some of the values, right? So, this is how you get from an element 139 00:07:13,710 --> 00:07:17,920 constraints of course, you know we don't require option five. 140 00:07:17,920 --> 00:07:19,980 And then you see so the capacity constraint is there. 141 00:07:19,980 --> 00:07:23,508 We know that the production, the [INAUDIBLE], the capacity constraints on 142 00:07:23,508 --> 00:07:28,216 that production unit is one out of three. So if this car, the first car requires 143 00:07:28,216 --> 00:07:31,978 option three we know that the next two, the next two slots cannot require option 144 00:07:31,978 --> 00:07:35,782 three, okay. And so this is essentially these two 145 00:07:35,782 --> 00:07:39,373 constraints basically acting as soon as you are actually giving a value to a 146 00:07:39,373 --> 00:07:44,222 particular variable. This constraint is actually already 147 00:07:44,222 --> 00:07:47,876 acting as well, because it made, it removed all the other, it makes sure that 148 00:07:47,876 --> 00:07:53,000 none of the other slot can be assigned of a car of type one. 149 00:07:53,000 --> 00:07:54,921 Okay. Now, this is more propagation that I'm 150 00:07:54,921 --> 00:07:57,510 going to show you. Okay, so you know, this is the demand 151 00:07:57,510 --> 00:08:01,084 constraints that I told you about. That's why these values were removed, 152 00:08:01,084 --> 00:08:03,224 okay. And then you see this is very interesting 153 00:08:03,224 --> 00:08:05,097 what is happening here. Okay. 154 00:08:05,097 --> 00:08:09,897 So what you have been deducing here is that, you cannot have a car of class five 155 00:08:09,897 --> 00:08:16,130 and six on the second slot, and the reason is because option one. 156 00:08:16,130 --> 00:08:17,980 Right? So you see option one over here. 157 00:08:17,980 --> 00:08:20,759 Okay. So option one, I know that I cannot take 158 00:08:20,759 --> 00:08:23,990 option one. That's what I see over there. 159 00:08:23,990 --> 00:08:27,820 I cannot take option one there because of the one out of two constraints. 160 00:08:27,820 --> 00:08:30,652 And essentially that tells you, which this is telling you which car are 161 00:08:30,652 --> 00:08:34,650 actually requesting option one. And of course you have class, you have 162 00:08:34,650 --> 00:08:39,022 class five and six over here, okay? And therefore you can remove these guys 163 00:08:39,022 --> 00:08:42,694 from consideration for the slot, for, for the, for the inside the, inside the var, 164 00:08:42,694 --> 00:08:47,720 inside the values of the assembly line. Okay, so you made that deduction and you 165 00:08:47,720 --> 00:08:51,930 made a similar deduction here for class five, for the third slot over there. 166 00:08:51,930 --> 00:08:55,560 Okay, so once again, all this propagation is being done by the system behind the 167 00:08:55,560 --> 00:08:57,632 scene. Okay. 168 00:08:57,632 --> 00:09:00,656 Now, so with these beautiful examples that I talked about, the first time we 169 00:09:00,656 --> 00:09:04,466 run this example, you know, I rem, I still remember it, you know. 170 00:09:04,466 --> 00:09:07,568 [UNKNOWN] would work, looking at the screen, and with this beautiful assembly 171 00:09:07,568 --> 00:09:11,602 line, and the system would produce these cars [SOUND] almost to the end. 172 00:09:11,602 --> 00:09:15,342 And then, just when it was about to reach the solution, it would backtrack and come 173 00:09:15,342 --> 00:09:18,132 back. And then it would do that for, you know, 174 00:09:18,132 --> 00:09:21,426 half an hour. And were like, why isn't it never finding 175 00:09:21,426 --> 00:09:22,909 a solution? Okay. 176 00:09:22,909 --> 00:09:26,930 And then we started analyzing, looking at the screen for hours at a time, okay. 177 00:09:26,930 --> 00:09:29,891 And what we realized is that the system was actually doing something pretty 178 00:09:29,891 --> 00:09:32,820 stupid. Actually the model was pretty stupid. 179 00:09:32,820 --> 00:09:36,065 We wrote a bad model and, but we did use a very important feature of these 180 00:09:36,065 --> 00:09:38,973 constraints. So, and so this is what we found, found 181 00:09:38,973 --> 00:09:41,486 out, okay. So consider an option O and assume that 182 00:09:41,486 --> 00:09:45,980 it's capacity is two out of three, and that I have to produce 12 cars, okay. 183 00:09:45,980 --> 00:09:49,010 This is my assembly line. I have to produce 12 cars out of every 184 00:09:49,010 --> 00:09:53,435 three slots I can produce at most two. Okay, so what do I know? 185 00:09:53,435 --> 00:09:56,502 Okay. So I know that, in the last three slots, 186 00:09:56,502 --> 00:10:00,150 I can only produce two cars. Okay. 187 00:10:00,150 --> 00:10:02,630 So, that I know, and therefore, what do I know? 188 00:10:02,630 --> 00:10:06,720 I know also, so I can produce only these two cars on the last two slot. 189 00:10:06,720 --> 00:10:07,970 Okay. So what do I know? 190 00:10:07,970 --> 00:10:10,230 What do I have to produce in the beginning? 191 00:10:10,230 --> 00:10:12,800 Well, I have to produce ten cars in the beginning. 192 00:10:12,800 --> 00:10:15,920 So I know that I have at least to produce these ten cars. 193 00:10:15,920 --> 00:10:18,210 Because if I don't, I won't find a solution. 194 00:10:18,210 --> 00:10:20,567 And that's what the system was doing. It was putting car, no not putting the 195 00:10:20,567 --> 00:10:22,997 car, not putting the car. And it was coming here and scrambling 196 00:10:22,997 --> 00:10:25,405 around trying to put these cars, but it couldn't, okay. 197 00:10:25,405 --> 00:10:28,882 So now, I know that I have to put at least ten cars in this particular pla, in 198 00:10:28,882 --> 00:10:32,710 this particular part of the assembly line. 199 00:10:32,710 --> 00:10:33,970 Okay. So what else can I deduce? 200 00:10:33,970 --> 00:10:36,690 Well, I can do exactly the same reasoning, right? 201 00:10:36,690 --> 00:10:40,780 So, I can deduce that I can, at most, put two cars over there. 202 00:10:40,780 --> 00:10:42,940 Therefore, I have to produce eight cars over there. 203 00:10:42,940 --> 00:10:46,214 And I can continue the reasoning. So I'm deducing a lot of constraints on 204 00:10:46,214 --> 00:10:49,460 the assembly line. For every one of these portion of the 205 00:10:49,460 --> 00:10:52,534 assembly line. I know how much car I can produce, and I 206 00:10:52,534 --> 00:10:55,880 have to produce, okay. Now, is it easy to actually add these 207 00:10:55,880 --> 00:10:57,880 constraints? Yes, it's very easy. 208 00:10:57,880 --> 00:10:59,950 Essentially, what you are doing here is counting. 209 00:10:59,950 --> 00:11:03,330 It's just the same kind of constraints that we did for expressing the capacity 210 00:11:03,330 --> 00:11:06,502 constraints. But this time around, what I know is that 211 00:11:06,502 --> 00:11:10,940 I'm putting a constraint which is not limiting the number of car by both. 212 00:11:10,940 --> 00:11:13,640 I'm actually limiting the number of car by below. 213 00:11:13,640 --> 00:11:16,650 And so, what you see here is a constraints where essentially, you know? 214 00:11:16,650 --> 00:11:21,642 I'm iteratively looking at larger, and larger portion of the assembly line, 215 00:11:21,642 --> 00:11:25,817 okay. actually, smaller on the left, larger on 216 00:11:25,817 --> 00:11:27,420 the right. Okay. 217 00:11:27,420 --> 00:11:31,260 And for every one of them I'm basically deducing, you know, how much I can 218 00:11:31,260 --> 00:11:37,760 produce on the right side, and make sure that the left side is producing enough. 219 00:11:37,760 --> 00:11:40,230 So I'm basically taking the lower bond, multiplying by I. 220 00:11:40,230 --> 00:11:42,950 I'm taking the upper bond, multiplying by I as well. 221 00:11:42,950 --> 00:11:45,958 When I am actually limiting the, the, the search, the, the, the slots that I'm 222 00:11:45,958 --> 00:11:49,480 considering. Okay, now that constraint was really 223 00:11:49,480 --> 00:11:52,114 powerful. When we actually run the model like this, 224 00:11:52,114 --> 00:11:55,890 it would find all the solutions to the benchmark that we had very quickly. 225 00:11:55,890 --> 00:11:59,050 And you can see why, right. So this is the assembly line, okay. 226 00:11:59,050 --> 00:12:02,100 So I placing the second queen and I'm start deducing information, okay. 227 00:12:02,100 --> 00:12:05,280 The second, the second car and I'm placing it there. 228 00:12:05,280 --> 00:12:08,706 Okay, so once again I remove value. I'm propagating some of these constraints 229 00:12:08,706 --> 00:12:10,860 over there. I know that I need these options. 230 00:12:10,860 --> 00:12:13,710 This is two out of five. I remove some values, okay. 231 00:12:13,710 --> 00:12:16,660 So I deduce a lot of values like this, okay. 232 00:12:16,660 --> 00:12:19,860 And then I can remove some more values using this particular options that you 233 00:12:19,860 --> 00:12:23,236 see there, right? So this is, once again, option number 234 00:12:23,236 --> 00:12:25,448 four. I know that I can't take, I, I, I, you 235 00:12:25,448 --> 00:12:28,828 know, I, I have information of this, I use this particular option to these more 236 00:12:28,828 --> 00:12:32,020 values and this is what I do. Okay. 237 00:12:32,020 --> 00:12:35,830 And then, essentially, the, the very interesting thing happens here. 238 00:12:35,830 --> 00:12:37,846 Okay. So look at this, okay I have to produce 239 00:12:37,846 --> 00:12:42,624 two cars of these three classes, okay. And these cars are actually, you know, 240 00:12:42,624 --> 00:12:46,770 all using option two, okay. So, in option two I know that I have to 241 00:12:46,770 --> 00:12:50,600 produce six cars, okay. Now, look at the assembly line and option 242 00:12:50,600 --> 00:12:52,450 two here, okay. What do I know? 243 00:12:52,450 --> 00:12:57,410 Well, I know that I can at most, at most put two in here, okay. 244 00:12:57,410 --> 00:13:01,685 So, which basically means that. You know, in the first part of the 245 00:13:01,685 --> 00:13:03,960 assembly line, I have to put four. Okay. 246 00:13:03,960 --> 00:13:07,448 Once again, I play the same three. In these first three slides, slots, I can 247 00:13:07,448 --> 00:13:13,130 at most put two, and then essentially, at the rest, I have also to put two. 248 00:13:13,130 --> 00:13:16,780 Okay, at most, at least two. This was at most, this is at least. 249 00:13:16,780 --> 00:13:20,316 Now look at this tiny thing here, okay. So I have two slots and I have to produce 250 00:13:20,316 --> 00:13:22,710 at most two. Well, that's easy, right. 251 00:13:22,710 --> 00:13:24,510 I have to put these things over there. Okay. 252 00:13:24,510 --> 00:13:26,320 If I put two over there. Okay. 253 00:13:26,320 --> 00:13:28,980 This is a two out of three, so I cannot put that one. 254 00:13:28,980 --> 00:13:31,750 Now, I have to put two in this thing, and there are only two slots, I put them. 255 00:13:31,750 --> 00:13:35,694 And then essentially all the options you know, all the various options for these, 256 00:13:35,694 --> 00:13:41,090 all the particular value for these options have been fixed at this time. 257 00:13:41,090 --> 00:13:43,713 Now I can start propagating that information to both, and this is what you 258 00:13:43,713 --> 00:13:45,570 are seeing here. Okay. 259 00:13:45,570 --> 00:13:48,950 So tremendous, tremendous reduction of the search space. 260 00:13:48,950 --> 00:13:51,134 Okay. So that constraint, essentially, that 261 00:13:51,134 --> 00:13:53,970 what we did was basically doing two things. 262 00:13:53,970 --> 00:13:56,868 It was basically looking at the capacity constraints on the line, it was basically 263 00:13:56,868 --> 00:14:01,018 looking at the demand constraints. Merging these two to actually derive a 264 00:14:01,018 --> 00:14:04,474 new property of the solution, and then essentially what happened is that the 265 00:14:04,474 --> 00:14:07,940 search base would be dramatically reduced. 266 00:14:07,940 --> 00:14:10,050 Okay. And the system would find solution very, 267 00:14:10,050 --> 00:14:11,473 very quickly. Okay. 268 00:14:11,473 --> 00:14:14,825 So you see it's continuing. This thing just propagates at this point, 269 00:14:14,825 --> 00:14:16,490 on its own. Right? 270 00:14:17,530 --> 00:14:18,820 It will never stop. Okay. 271 00:14:18,820 --> 00:14:22,785 So what we did here is essentially taking two constraints and merging them for 272 00:14:22,785 --> 00:14:26,914 improving the communication between them. Okay. 273 00:14:26,914 --> 00:14:32,550 So, so, the various, so let me summarize what we have seen so far. 274 00:14:32,550 --> 00:14:35,240 So we have seen various way of improving the communication. 275 00:14:35,240 --> 00:14:38,072 One of them is actually introducing global constraints, you merge two 276 00:14:38,072 --> 00:14:39,473 constraints. Okay. 277 00:14:39,473 --> 00:14:42,307 Another way is actually adding in redundant constraints. 278 00:14:42,307 --> 00:14:45,215 That' what you have seen. Then we could add surrogate constraints, 279 00:14:45,215 --> 00:14:48,694 that's merging two constraints, you know, for instance taking a linear combination 280 00:14:48,694 --> 00:14:51,404 of them. Adding a new one, and then implied 281 00:14:51,404 --> 00:14:54,563 constraint is, is just what I've talked to you about now. 282 00:14:54,563 --> 00:14:57,735 It's you take two constraints and you derive a property from them. 283 00:14:57,735 --> 00:15:00,817 Okay, so that's all the ways we can actually exploit the various, the various 284 00:15:00,817 --> 00:15:03,853 the various constraints that you have an combine them, to actually improve the 285 00:15:03,853 --> 00:15:07,750 communication. Okay, let me talk about one last thing, 286 00:15:07,750 --> 00:15:11,409 which is duel modeling. Which is eh, essentially, pushing this 287 00:15:11,409 --> 00:15:13,978 idea, to the extreme. Okay, so sometimes you look at a 288 00:15:13,978 --> 00:15:16,515 particular problem, and you have different way of modeling it, and you 289 00:15:16,515 --> 00:15:19,210 don't know which one is the best. Okay. 290 00:15:19,210 --> 00:15:21,590 So you don't have the same decision variable. 291 00:15:21,590 --> 00:15:23,710 You don't express the constraint in the same way. 292 00:15:23,710 --> 00:15:26,040 So, what do you do? Well, in constraint programing, one of 293 00:15:26,040 --> 00:15:28,130 the nice things you can do is just not borrow. 294 00:15:28,130 --> 00:15:31,406 You, essentially, put the two model inside a system. 295 00:15:31,406 --> 00:15:33,155 Okay. It's too hard to choose [INAUDIBLE] 296 00:15:33,155 --> 00:15:36,179 between them, it's, you know, some constraints are naturally expressed in 297 00:15:36,179 --> 00:15:39,818 one and not in the other one. Just put the two models, and connect them 298 00:15:39,818 --> 00:15:41,880 in some fashion. Okay. 299 00:15:41,880 --> 00:15:45,114 So essentially the basic idea of doing modeling is that if you have several ways 300 00:15:45,114 --> 00:15:48,348 of modeling a problem, put them in, link them through constraints, and see what 301 00:15:48,348 --> 00:15:50,590 you get. Okay. 302 00:15:50,590 --> 00:15:54,270 Because here we exploit the strengths of both models. 303 00:15:54,270 --> 00:15:56,621 If you have three, you can put three. Okay. 304 00:15:56,621 --> 00:15:59,700 So let me show you a very, very simple example of that. 305 00:15:59,700 --> 00:16:02,118 You know, we come back to the queens problem that we're starting from in the 306 00:16:02,118 --> 00:16:04,645 first. In the first two lectures from constraint 307 00:16:04,645 --> 00:16:06,876 programming. The, you know, I told you that time that 308 00:16:06,876 --> 00:16:10,044 there were many modeling of, you know, the eight queens problem, and one of them 309 00:16:10,044 --> 00:16:13,260 was to associate a column associate a queen for every column and the decision 310 00:16:13,260 --> 00:16:18,300 variable would denote the row. And that's one modeling, okay. 311 00:16:18,300 --> 00:16:20,604 And that essentially, the constraint would say, oh, you know, you know, the, 312 00:16:20,604 --> 00:16:24,220 the queen's going to be on the same row, upper diagonal or lower diagonal. 313 00:16:24,220 --> 00:16:25,870 Here is another modeling. Okay. 314 00:16:25,870 --> 00:16:29,032 So instead of us assigning a queen to every column, I assign a queen to every 315 00:16:29,032 --> 00:16:30,590 row. Okay. 316 00:16:30,590 --> 00:16:33,390 I have a completely different model. Now I'm resigning about the row. 317 00:16:33,390 --> 00:16:35,769 And of course, you know, the queens on the row can not be on the same column, 318 00:16:35,769 --> 00:16:38,820 and once again you will have diagonal constraints. 319 00:16:38,820 --> 00:16:40,630 Okay, let me show you the model. This is the model. 320 00:16:40,630 --> 00:16:42,380 Okay. Two sets of variables, no? 321 00:16:42,380 --> 00:16:44,326 Okay. You will see the row variables and the 322 00:16:44,326 --> 00:16:45,760 column variables. Okay. 323 00:16:45,760 --> 00:16:49,210 The row variables are basically for every column it specifies, you know, the row in 324 00:16:49,210 --> 00:16:53,940 which the queen is going to be placed. The column variable, okay, so for every 325 00:16:53,940 --> 00:16:58,230 row it's going to specify the column in which the queen is placed. 326 00:16:58,230 --> 00:17:00,120 Okay. And then you see the constraints here. 327 00:17:00,120 --> 00:17:03,050 The constraints are on the two sets of variables, they are exactly the same. 328 00:17:03,050 --> 00:17:05,776 You know, kind of, right? Some are on the row, some are on the 329 00:17:05,776 --> 00:17:08,355 column, but they're really, really the same. 330 00:17:08,355 --> 00:17:10,552 Okay. And then the really important, the really 331 00:17:10,552 --> 00:17:14,190 important part is the last constraint that you see is there. 332 00:17:14,190 --> 00:17:16,970 And that part is, essentially connecting the two model. 333 00:17:16,970 --> 00:17:20,540 So, you have the row model, so far. You have the column model over there. 334 00:17:20,540 --> 00:17:22,920 But they are not connected. This makes them connected. 335 00:17:22,920 --> 00:17:25,800 So, from what you have learned from the model, is going to be transferred into 336 00:17:25,800 --> 00:17:28,920 the other and vice versa. How are they connected? 337 00:17:28,920 --> 00:17:31,710 They are connected by these constraints. What are these constraints saying? 338 00:17:31,710 --> 00:17:33,820 Take a row, take a column. Okay. 339 00:17:33,820 --> 00:17:38,098 So, if we know, that the row of column C is R, it has to be the case the column of 340 00:17:38,098 --> 00:17:41,032 R is equal to C. Okay. 341 00:17:41,032 --> 00:17:45,379 And of course, vice versa, vice versa, if you know that the column of R is C, it 342 00:17:45,379 --> 00:17:49,560 has to be the case that the row of C is R. 343 00:17:49,560 --> 00:17:51,386 Okay. So, in a sense, every time I learn 344 00:17:51,386 --> 00:17:55,115 something about the row, I'm going to learn something about the column. 345 00:17:55,115 --> 00:17:57,170 Okay, and vice versa. Okay. 346 00:17:57,170 --> 00:18:00,002 So in a sense, I get not only the propagation of both of these models, but 347 00:18:00,002 --> 00:18:04,559 I have information which propagates, you know from one model to the other one. 348 00:18:04,559 --> 00:18:07,775 Which can start a new deduction on one of them, and which can start, you know, also 349 00:18:07,775 --> 00:18:12,610 the deduction of the other one through these particular constraints. 350 00:18:12,610 --> 00:18:13,880 That's it. Thank you.