1 00:00:00,480 --> 00:00:05,210 Okay guys. Discrete Optimization Part VI, okay? 2 00:00:05,210 --> 00:00:08,655 So, once again what we're going to do is using the tools that we have built so far 3 00:00:08,655 --> 00:00:13,728 and trying to build better models, okay? So, we know some of the techniques that 4 00:00:13,728 --> 00:00:17,445 we have, and what I want to show you today is how to use redundant constraints 5 00:00:17,445 --> 00:00:23,370 to speed up models tremendously, okay? Now what is a redundant constraints? 6 00:00:23,370 --> 00:00:27,132 Okay, so essential these are constraints that don't add anything to your model 7 00:00:27,132 --> 00:00:31,942 from a semantics stand point. The model will have the same exact number 8 00:00:31,942 --> 00:00:36,280 of solutions, okay? But they are computationally significant 9 00:00:36,280 --> 00:00:40,490 because they will prove the search spacement role. 10 00:00:40,490 --> 00:00:43,230 So in a sense, so you put them in the model. 11 00:00:43,230 --> 00:00:46,510 They don't remove solution, but they decrease the search space. 12 00:00:46,510 --> 00:00:49,090 And so once you find these constraints, they are very, very useful from a 13 00:00:49,090 --> 00:00:52,900 computational standpoint. Of course, the question is how do I find 14 00:00:52,900 --> 00:00:55,322 that? And in general, they capture really 15 00:00:55,322 --> 00:00:59,549 interesting properties of the solution. You look at your problem and you say, oh, 16 00:00:59,549 --> 00:01:04,240 but four, you know something to be a feasible solution it has to satisfy this. 17 00:01:04,240 --> 00:01:06,850 And typically that's a constraint, you take that constraints. 18 00:01:06,850 --> 00:01:09,610 You've put it in the model and in Constraint Programming the more you put 19 00:01:09,610 --> 00:01:13,040 inside the model the faster your compilation is going to be. 20 00:01:14,260 --> 00:01:16,930 So it's a pretty good aspect of Constraint Programming. 21 00:01:16,930 --> 00:01:20,050 Most of the time you try to capture as tightly as possible this set of solutions 22 00:01:20,050 --> 00:01:23,533 by expressing the constraints as best as you can, okay? 23 00:01:23,533 --> 00:01:27,320 So I'm going to use a couple of simple examples, you know to illustrate this. 24 00:01:27,320 --> 00:01:30,146 You know, remember the magic series, okay? 25 00:01:30,146 --> 00:01:34,562 So we want you to find numbers from S0 to Sn such that Si represent the number of 26 00:01:34,562 --> 00:01:40,750 occurrences of i inside the series, okay? So I asked you last time you, we could 27 00:01:40,750 --> 00:01:44,414 actually find this series, this is a beautiful one, okay? 28 00:01:44,414 --> 00:01:47,600 So we see you know, there are two instances of 0, took, took, there is one 29 00:01:47,600 --> 00:01:52,440 instance of one itself, there is two instances of two you know, itself. 30 00:01:52,440 --> 00:01:56,060 And the first one, okay? And there are reviews 0 instan, 0 31 00:01:56,060 --> 00:01:59,560 occurrences of 3, 0 occurrences of 4, okay? 32 00:01:59,560 --> 00:02:02,360 Now, so this is the model that we saw last time. 33 00:02:02,360 --> 00:02:05,898 And what I was you know? One of the things that I'm asking you, 34 00:02:05,898 --> 00:02:10,270 is, can you find the properties that the solutions have to satisfy. 35 00:02:10,270 --> 00:02:13,740 Now when you look at the, you know, the array of decision variables series. 36 00:02:13,740 --> 00:02:16,790 Can you find a constraints that is actually helping, you know, will help, 37 00:02:16,790 --> 00:02:19,640 you know, in addition to these constraints that we have, that we have 38 00:02:19,640 --> 00:02:22,656 stated. So we have these constraints which are 39 00:02:22,656 --> 00:02:25,200 stated, it actually capture exactly what are the solution. 40 00:02:25,200 --> 00:02:29,287 But can I, can I find another constraint which is always true for every solution, 41 00:02:29,287 --> 00:02:33,930 but which will give the solver much more information? 42 00:02:33,930 --> 00:02:36,782 And that basically means the solver will be ab, able to explore it to remove 43 00:02:36,782 --> 00:02:40,849 values from the domain of the variables. Because that's the end of you know, 44 00:02:40,849 --> 00:02:43,554 that's the rule of the game essentially, okay? 45 00:02:43,554 --> 00:02:47,520 So, typically you know, the way you do this is that you exaggerate, right? 46 00:02:47,520 --> 00:02:51,369 So look at this thing, okay? So this is my magic series and I'm asking 47 00:02:51,369 --> 00:02:55,707 you, can I put 17 there, right? I'm exaggerating right, so nobody would 48 00:02:55,707 --> 00:02:58,668 do that, okay? I put 2000 there, you know, it makes no 49 00:02:58,668 --> 00:02:59,940 sense. Why? 50 00:02:59,940 --> 00:03:05,662 Because what is 17 denoting there? 17 would denote the number of occurrences 51 00:03:05,662 --> 00:03:10,880 of 4 in the series, no that series is you know 5, of length 5. 52 00:03:10,880 --> 00:03:16,360 If I put 17 of [UNKNOWN] on one variable to put 17 occurrences of 4, okay? 53 00:03:16,360 --> 00:03:19,936 So, in a sense, what do I know? Can I get you something which is 54 00:03:19,936 --> 00:03:23,730 interesting on the sum of the numbers on this series? 55 00:03:23,730 --> 00:03:27,490 Yes, they are all occurrences. How many occurrence can I have? 56 00:03:27,490 --> 00:03:31,958 Well the length of the series, okay? So I can have this beautiful essentially 57 00:03:31,958 --> 00:03:35,926 constraint which says that the sum of all the elements in the series have to be 58 00:03:35,926 --> 00:03:40,570 equal to the length of the series which is n, okay? 59 00:03:40,570 --> 00:03:44,770 So these constraints has to be true, it must be true, there is no other way. 60 00:03:44,770 --> 00:03:47,026 Okay, so the number of occurrences n, okay? 61 00:03:47,026 --> 00:03:50,302 And since these guys, these decision variables, are denoting the number of 62 00:03:50,302 --> 00:03:53,950 occurrences okay, the sum of them can not be more than n. 63 00:03:53,950 --> 00:03:57,430 So this is a constraint which is redundant from a semantic standpoint. 64 00:03:57,430 --> 00:03:59,580 It will never, never remove any solutions. 65 00:03:59,580 --> 00:04:01,570 Every solution will satisfy those constraints. 66 00:04:01,570 --> 00:04:06,018 But it will be able to prune the search base better, okay? 67 00:04:06,018 --> 00:04:10,750 So, can I do better than this, okay? Can I find actually something which is 68 00:04:10,750 --> 00:04:13,276 stronger than that? Look at this thing, okay? 69 00:04:13,276 --> 00:04:16,930 So what am I writing? Assume that series 2 is equal to 3. 70 00:04:16,930 --> 00:04:20,195 What does that really mean? That basically means that the value here, 71 00:04:20,195 --> 00:04:23,040 okay. I'm going to put the 3 over there, okay? 72 00:04:23,040 --> 00:04:28,828 What does it mean? It means, essentially, that there are 3, 73 00:04:28,828 --> 00:04:33,480 2 in this array, okay? So far so good, that's what we know. 74 00:04:33,480 --> 00:04:37,970 But saying that there are three, two's in this array means what? 75 00:04:37,970 --> 00:04:42,666 How many occurrences that, that call for. Well essentially, you know, these guys, 76 00:04:42,666 --> 00:04:47,054 you know, there are three two's, okay? Two occurrences, and there are that three 77 00:04:47,054 --> 00:04:50,522 times, so that means there are six occurrences, okay? 78 00:04:50,522 --> 00:04:54,398 So essentially what we know is that there is another way for actually counting the 79 00:04:54,398 --> 00:04:58,540 number of occurrences. Instead of summing every element in the 80 00:04:58,540 --> 00:05:03,297 series, what you could do is look at the re-element in the series, okay? 81 00:05:03,297 --> 00:05:06,024 And then multiply by i. So you look at every element of the 82 00:05:06,024 --> 00:05:09,048 series, let's say element i, and you multiply it by i, because what you, what 83 00:05:09,048 --> 00:05:12,300 I had before was what, series two was three. 84 00:05:12,300 --> 00:05:16,630 So, I multiplied by two, so that makes six occurrences, okay? 85 00:05:16,630 --> 00:05:21,650 So it's another way of computing the same information, okay? 86 00:05:21,650 --> 00:05:25,808 So I have another redundant constraint, which is basically the summation of i, 87 00:05:25,808 --> 00:05:30,029 you know, times series i, has to be equal to the number of occurrences, which is n, 88 00:05:30,029 --> 00:05:34,235 okay? So that's another concern, which one of 89 00:05:34,235 --> 00:05:36,954 the two that I've shown you before is stronger, okay? 90 00:05:36,954 --> 00:05:39,841 I will tell you a little bit which one is stronger, okay? 91 00:05:39,841 --> 00:05:42,750 But it doesn't matter, right? We could put the first one, we could put 92 00:05:42,750 --> 00:05:45,585 the second one inside the server and let the server propagate these two, two 93 00:05:45,585 --> 00:05:49,534 constraints at the same time. Okay, so let me show you the kind of 94 00:05:49,534 --> 00:05:53,056 deduction that we can do. Okay, so this is essentially only taking 95 00:05:53,056 --> 00:05:56,110 the second one here, okay? Which is stronger in almost all the 96 00:05:56,110 --> 00:06:00,890 cases, there's one case where it is not, but almost all the cases it is stronger. 97 00:06:00,890 --> 00:06:03,696 So you see essentially the constraint reduction before, but you see this 98 00:06:03,696 --> 00:06:08,650 redundant constraint which is over there. Okay, what is interesting is what? 99 00:06:08,650 --> 00:06:13,151 You see a five there and you see that this guy is multiplied by four, right? 100 00:06:13,151 --> 00:06:15,958 What does that mean? Okay, that means that the maximum value 101 00:06:15,958 --> 00:06:19,770 that series 4 can take is what? Well, it's one, right? 102 00:06:19,770 --> 00:06:23,109 And the same thing for series 3, and for series 2 the maximum value is going to be 103 00:06:23,109 --> 00:06:26,840 two, okay? Otherwise I will exceed these five, okay? 104 00:06:26,840 --> 00:06:29,490 And for one it's going to be, you know, five, okay? 105 00:06:29,490 --> 00:06:33,309 So immediately, I can deduce very strong information here, on the value of these 106 00:06:33,309 --> 00:06:36,793 variables, okay? And I can use that for pruning the search 107 00:06:36,793 --> 00:06:40,110 page [SOUND]. Very quickly, many of these ray file 108 00:06:40,110 --> 00:06:44,248 constraints can disappear, okay? Because I know that they can't be true, 109 00:06:44,248 --> 00:06:47,040 okay? So essentially, here, you know, I have 110 00:06:47,040 --> 00:06:50,440 removed about a third of these constraints, okay? 111 00:06:50,440 --> 00:06:52,880 Then, assume that I make a very simple choice. 112 00:06:52,880 --> 00:06:57,460 I say that series 0 is equal to 2, okay? So that basically means that I put a 2 113 00:06:57,460 --> 00:07:01,300 over there, right? So, you see the 2 over there, okay? 114 00:07:01,300 --> 00:07:05,226 It also means that I have a 2, right? And therefore, the value that we see here 115 00:07:05,226 --> 00:07:09,210 for series 2 here I have already one over there, okay? 116 00:07:09,210 --> 00:07:12,158 And then, you look at the constraints, you know, the redundant constraints that 117 00:07:12,158 --> 00:07:15,030 I have added, okay? So, what do you see there? 118 00:07:15,030 --> 00:07:18,650 I know that series 2 is greater than 0 now, okay? 119 00:07:18,650 --> 00:07:23,340 So, and therefore, when you look at these constraints, essentially the 5 has become 120 00:07:23,340 --> 00:07:27,105 a 3, okay? And therefore, I can immediately deduce, 121 00:07:27,105 --> 00:07:30,212 okay, that series 4 here has to be equal to 0. 122 00:07:30,212 --> 00:07:34,118 Because it multiplied by a coefficient 4, and it can be at most 3, and that the 123 00:07:34,118 --> 00:07:39,380 other one, the 3 times series, 3 can be at most, you know, 1, okay? 124 00:07:39,380 --> 00:07:42,674 So once again, I can use that information and I can start propagating that 125 00:07:42,674 --> 00:07:46,670 information, and my search base becomes much smaller, okay? 126 00:07:46,670 --> 00:07:50,266 So, if you use the simple model that I've just shown you, you can solve magic 127 00:07:50,266 --> 00:07:53,684 series up to really, really large numbers. 128 00:07:53,684 --> 00:07:57,338 And if you do that, if you actually implement this beautiful model, you will 129 00:07:57,338 --> 00:08:01,282 see a very nice pattern in the way these solutions are actually being so, so, so 130 00:08:01,282 --> 00:08:05,978 basically constructed. And the similarities that they have with 131 00:08:05,978 --> 00:08:08,455 each other. Okay, so the first role of Redundant 132 00:08:08,455 --> 00:08:12,440 Constraints is to express properties of the solution. 133 00:08:12,440 --> 00:08:15,476 And because it, it looks at the problem, the redundant constraint is looking at 134 00:08:15,476 --> 00:08:19,425 the problem from a different angle, it's going to boost the propagation. 135 00:08:19,425 --> 00:08:22,729 Okay, so in a sense what you are, you know, what you are adding is this new 136 00:08:22,729 --> 00:08:27,174 constraint inside the overall model. You had all these constraints which were 137 00:08:27,174 --> 00:08:29,282 already there. They were proving the search case 138 00:08:29,282 --> 00:08:31,505 independently. You add the new one and that one will 139 00:08:31,505 --> 00:08:35,900 also reduce these domains and therefore will have an impact on the other one. 140 00:08:35,900 --> 00:08:39,220 That's the first rule of redundant constraint, okay? 141 00:08:39,220 --> 00:08:42,229 So, I'm going to show you another role, this is the second role, which is to 142 00:08:42,229 --> 00:08:45,450 provide a global view, a more global view okay? 143 00:08:45,450 --> 00:08:48,270 So, and what I'm going to show you is that you can actually combine existing 144 00:08:48,270 --> 00:08:51,118 constraints. And that combination will improve your 145 00:08:51,118 --> 00:08:53,780 communication between the various variables okay? 146 00:08:53,780 --> 00:08:57,510 So, this is, I'm going to illustrate with a market split problem, okay? 147 00:08:59,080 --> 00:09:01,918 and essentially once again, so you can think of it as a multi knapsack except 148 00:09:01,918 --> 00:09:04,627 that the constraints, instead of being small or equal are going to be equal, 149 00:09:04,627 --> 00:09:07,692 okay? So what you have is a set of constraints, 150 00:09:07,692 --> 00:09:10,662 a set of you know, you will have a set of constraints, you know, indexed by C, a 151 00:09:10,662 --> 00:09:15,418 set of variables indexed by V, okay? For every value in C and V, you will have 152 00:09:15,418 --> 00:09:19,252 have essentially a weight, okay? You can think of an abstract in the 153 00:09:19,252 --> 00:09:22,578 multiple dimensions, dimensions, that's a WCV, okay? 154 00:09:22,578 --> 00:09:26,710 And then you have a right in sight, you can think of it as a capacity, okay? 155 00:09:26,710 --> 00:09:29,530 And then the decision variables are going to be this value X. 156 00:09:29,530 --> 00:09:32,140 There is one variable for every element of V, okay? 157 00:09:32,140 --> 00:09:35,640 And then the constraints are essentially kind of knapsack constraints except that 158 00:09:35,640 --> 00:09:40,106 it's an equality and not a second equal. But what you do is you basically multiply 159 00:09:40,106 --> 00:09:43,390 the weight and the variable, okay, for everyone of these concerns. 160 00:09:43,390 --> 00:09:46,800 And you want that to be equal to the right hand side, okay? 161 00:09:46,800 --> 00:09:50,222 Now these constraints are actually pretty, pretty weak from a, from a 162 00:09:50,222 --> 00:09:53,757 propagation standpoint. They don't communicate each, to each 163 00:09:53,757 --> 00:09:56,822 other, only through the domain. And in this particular case, you have 164 00:09:56,822 --> 00:10:00,130 this linear concern that I'm basically doing their work independently. 165 00:10:00,130 --> 00:10:04,075 And they communicate very later, okay? So one of the thing you can do, okay, is 166 00:10:04,075 --> 00:10:08,770 use the concept of surrogate constraints. So you take all these constraints and you 167 00:10:08,770 --> 00:10:12,200 add them, everyone with a different coefficient, okay? 168 00:10:12,200 --> 00:10:16,620 So I'm basically using here, you know, alpha to the power of C, okay? 169 00:10:16,620 --> 00:10:19,348 And by essentially multiplying the first constraint by alpha, the second 170 00:10:19,348 --> 00:10:22,164 constraint by alpha squared, the total constraint by alpha cubed, and so on, 171 00:10:22,164 --> 00:10:25,210 okay? I can combine all these constraints. 172 00:10:25,210 --> 00:10:28,845 I also multiply the right, the right sorry, the right insight here. 173 00:10:28,845 --> 00:10:32,151 And therefore, this is essentially a combination of all the, a linear 174 00:10:32,151 --> 00:10:36,920 combination of all the existing constraints, and it's valid, obviously. 175 00:10:36,920 --> 00:10:40,150 It's not going to remove any solution, and I can add it to the solver. 176 00:10:40,150 --> 00:10:42,644 So what I did was essentially take in constraints that are completely 177 00:10:42,644 --> 00:10:46,034 independent, merging them together. And now they are working on the same set 178 00:10:46,034 --> 00:10:49,328 of variables and they are going to prove the search base more, okay? 179 00:10:49,328 --> 00:10:52,490 So, Surrogate constraints, using Constraint Programming they are using 180 00:10:52,490 --> 00:10:56,780 Mathematically Programming as well we might talk about that later on, okay. 181 00:10:56,780 --> 00:11:00,044 But essentially what I'm doing is simple combination you know in this particular 182 00:11:00,044 --> 00:11:03,429 case, linear combination of existing constraints, okay? 183 00:11:03,429 --> 00:11:06,484 So in a sense, a Surrogate constraints is just a new constraint that I add, like 184 00:11:06,484 --> 00:11:09,940 the properties of the solution that I shown you before. 185 00:11:09,940 --> 00:11:13,108 Except that this time I'm not expressing a properties of the solution per say as 186 00:11:13,108 --> 00:11:16,608 something that I discover. I simply taking existing constraints and 187 00:11:16,608 --> 00:11:19,212 combining them and getting this new constraints that I am putting inside a 188 00:11:19,212 --> 00:11:23,590 constraint ,solver. Once again by definition, if I add new 189 00:11:23,590 --> 00:11:26,690 constraints the only thing that can happen is that I prove more in the worst 190 00:11:26,690 --> 00:11:30,683 case I prove the same, okay? And so in some application, it can make a 191 00:11:30,683 --> 00:11:33,410 big difference. Thank you.