1 00:00:00,340 --> 00:00:04,750 Okay, so this is Discrete Optimization: Constraint Programming, okay. 2 00:00:04,750 --> 00:00:08,208 so this is about global constraints. So, what we're going to do today is 3 00:00:08,208 --> 00:00:12,470 essentially give you the basic intuition on how to implement global constraints. 4 00:00:12,470 --> 00:00:15,290 And we'll consider two of them, Knapsack and All-different. 5 00:00:15,290 --> 00:00:18,910 Now, you have to understand that this is a huge area of research. 6 00:00:18,910 --> 00:00:22,506 There are about you know, more than 100 global constraints which have been 7 00:00:22,506 --> 00:00:25,700 defined so far. So this is only just touching upon the 8 00:00:25,700 --> 00:00:29,050 topic, but you'll get a sense of what it means to implement global constraints in 9 00:00:29,050 --> 00:00:34,320 a constraint programming system. Okay, so the golden standard for Pruning, 10 00:00:34,320 --> 00:00:37,776 this is the most important thing that we need to cover first is that, after the 11 00:00:37,776 --> 00:00:41,016 pruning, what we want to, what we want to have is that for every value in the 12 00:00:41,016 --> 00:00:46,170 domain of the variable x, that is left in the domain. 13 00:00:46,170 --> 00:00:49,290 So that value is still in the domain of variable x, we want to be sure that we 14 00:00:49,290 --> 00:00:52,514 can find values in the domain of the other variables in the constraint such 15 00:00:52,514 --> 00:00:56,974 that there is a feasible solution for that constraint. 16 00:00:56,974 --> 00:00:58,892 Okay? So in a sense, you know that every value 17 00:00:58,892 --> 00:01:02,258 for every variable you know, is part of a solution to that constraint, so that's 18 00:01:02,258 --> 00:01:06,630 the golden standard. Now, historically, you know, there are 19 00:01:06,630 --> 00:01:09,730 many names for that particular, for that particular golden standard, arc 20 00:01:09,730 --> 00:01:13,720 consistency, domain consistency, don't worry about those. 21 00:01:13,720 --> 00:01:16,395 We know that we have this golden standard that we want to achieve. 22 00:01:16,395 --> 00:01:19,360 Okay? In a sense that golden standard is, is 23 00:01:19,360 --> 00:01:23,080 basically capturing what it means to prune optimally, if you only have the 24 00:01:23,080 --> 00:01:25,850 domains. Okay? 25 00:01:25,850 --> 00:01:29,100 So there is, if you have only the domains and the constraint, there is no way you 26 00:01:29,100 --> 00:01:33,422 can actually have a better pruning. So, this is the notion of optimality that 27 00:01:33,422 --> 00:01:36,455 we have here. of course in practice, it may not be you 28 00:01:36,455 --> 00:01:40,930 know, possible to implement this global standard in polynomial time. 29 00:01:40,930 --> 00:01:45,010 So if that's the case, we'd have to relax the standards and you know, do incomplete 30 00:01:45,010 --> 00:01:49,725 pruning, or we left to you know, settle for exponential time. 31 00:01:49,725 --> 00:01:52,432 Okay? So, let me start with the binary 32 00:01:52,432 --> 00:01:55,162 knapsack, which is an example of that we are seeing, okay, so the constraint we 33 00:01:55,162 --> 00:01:59,455 have, you see it over there. We have a sum of the wk xk, xk are 34 00:01:59,455 --> 00:02:04,630 decision variables, taking value between 0 and 1, and we want essentially this big 35 00:02:04,630 --> 00:02:10,193 sum to be between L and U, okay? And so this is an example that I'm 36 00:02:10,193 --> 00:02:13,702 going to show you here, okay? And we're going to use later on in, in 37 00:02:13,702 --> 00:02:18,530 the lecture, you see the sum of the variable X1, and X2, and so on. 38 00:02:18,530 --> 00:02:21,830 And they have to be between 10 and 12. Okay. 39 00:02:21,830 --> 00:02:25,394 And so the first thing that we have to do right, because there is two things that a 40 00:02:25,394 --> 00:02:29,250 constraint is to do, is feasibility and then pruning. 41 00:02:29,250 --> 00:02:32,154 So the first thing is to find out if this constraint is feasible, and then we get, 42 00:02:32,154 --> 00:02:34,574 we have to see if we can remove some of the values of the domain of the 43 00:02:34,574 --> 00:02:38,516 variables, okay? Now to find out the, if this feasible, 44 00:02:38,516 --> 00:02:41,770 this is reasonably easy. I'm sure you can see it yourself. 45 00:02:41,770 --> 00:02:45,540 You give a one to these, you know, x2, x3 and x4, and you have a value of 12. 46 00:02:45,540 --> 00:02:48,438 This is between the bounds, so you are happy these constraints is feasible, 47 00:02:48,438 --> 00:02:50,908 okay? Now, the more interesting question here 48 00:02:50,908 --> 00:02:53,587 is that, can you actually remove some values from the domain of these 49 00:02:53,587 --> 00:02:56,700 variables? In other words, is there a variable which 50 00:02:56,700 --> 00:02:59,754 cannot take the value zero? Or is there a variable which cannot take 51 00:02:59,754 --> 00:03:01,590 the value one? Okay? 52 00:03:01,590 --> 00:03:04,210 So, think about it, okay? Can you see it? 53 00:03:04,210 --> 00:03:08,312 There is something to see here, okay? So, if you don't see it, don't worry, the 54 00:03:08,312 --> 00:03:10,952 algorithm is going to show it exactly what can be pruned in this particular 55 00:03:10,952 --> 00:03:13,951 example. Okay, so the, the, the basic algorithm 56 00:03:13,951 --> 00:03:16,879 that we're going to use for feasibility is based on dynamic programming, is 57 00:03:16,879 --> 00:03:20,902 going to pseudo-polynomial times. So if the numbers are small is basically 58 00:03:20,902 --> 00:03:23,912 polynomial time. If the numbers are big, s, you know, then 59 00:03:23,912 --> 00:03:26,730 the, the algorithm is going to take more time. 60 00:03:26,730 --> 00:03:29,950 the pruning algorithm is interesting, because essentially what it's doing, is 61 00:03:29,950 --> 00:03:32,894 using the dynamic programming table to prune the search, to pru, to prune the 62 00:03:32,894 --> 00:03:36,770 domain of the variables, okay? And so, the way to think about it, is 63 00:03:36,770 --> 00:03:39,586 we'll have two phases. The forward phase is going to compute 64 00:03:39,586 --> 00:03:42,610 essentially feasibility and its dependency graph. 65 00:03:42,610 --> 00:03:45,112 You know, what, you know, how do we, get to those values? 66 00:03:45,112 --> 00:03:47,021 Okay? And then we'd have a backward phases, 67 00:03:47,021 --> 00:03:50,678 which basically removes some of the things that we don't need. 68 00:03:50,678 --> 00:03:53,982 And then is going to basically show it, show it to you what values we have to 69 00:03:53,982 --> 00:03:58,086 prune, is going to be beautiful. You know, you'd see the pictures and then 70 00:03:58,086 --> 00:04:01,409 you'd see essentially what you can prune and what you cannot prune. 71 00:04:01,409 --> 00:04:05,121 So, in a sense when we talk about the algorithm here, essentially, it will 72 00:04:05,121 --> 00:04:09,540 basically combine feasibility and pruning in one algorithm. 73 00:04:09,540 --> 00:04:11,492 Okay? So this is, this is, this is the picture 74 00:04:11,492 --> 00:04:14,441 we're going to use. So, what we see here are the values from 75 00:04:14,441 --> 00:04:16,844 0 to 12, okay? That's all the values that we will 76 00:04:16,844 --> 00:04:18,670 consider. Okay? 77 00:04:18,670 --> 00:04:21,706 And these big circles that you see there, basically we are going to see if we can 78 00:04:21,706 --> 00:04:23,880 actually get there. Okay? 79 00:04:23,880 --> 00:04:26,904 So, initially what you have is that you have the set of all the values that you 80 00:04:26,904 --> 00:04:29,880 can get without actually picking any of the variables, with looking at the 81 00:04:29,880 --> 00:04:33,608 variables. And these are basically the values that 82 00:04:33,608 --> 00:04:37,053 you can reach by taking your value for x1 and then you will do the same for x2, x3, 83 00:04:37,053 --> 00:04:39,193 and x3. Okay? 84 00:04:39,193 --> 00:04:43,645 And then essentially at the end, you will see which values you can actually reach. 85 00:04:43,645 --> 00:04:45,720 Okay? So that's what we're going to do. 86 00:04:45,720 --> 00:04:47,923 Okay? So when we start of course, you know, if 87 00:04:47,923 --> 00:04:53,000 we don't use x1 or x2 or x3 or x4, the only value that we can get is zero. 88 00:04:53,000 --> 00:04:54,416 Okay? So we start from 0, that is the only 89 00:04:54,416 --> 00:04:58,674 value that we have at the beginning. Then we look at x1, and of course we can 90 00:04:58,674 --> 00:05:02,630 decide to take x1 or not to take x1, right? 91 00:05:02,630 --> 00:05:06,816 So when we if we, if we take x1 okay, so the value of x squared is 2. 92 00:05:06,816 --> 00:05:10,536 So it's so we can reach 2, and if you don't take x1 of course, we stay at 0 and 93 00:05:10,536 --> 00:05:14,730 that's what you see there. You see these two arrows. 94 00:05:14,730 --> 00:05:16,073 Okay? So one is going up. 95 00:05:16,073 --> 00:05:18,170 Okay? That's the arrow when we pick up x1, when 96 00:05:18,170 --> 00:05:21,470 x1 is equal to one, and we get reach re reach 2, in other words we still have 97 00:05:21,470 --> 00:05:24,920 zero. And you see that we use two different 98 00:05:24,920 --> 00:05:28,330 shape for these arrows, one is you know, a dash line, the other one is a solid 99 00:05:28,330 --> 00:05:31,250 line. And you'll see why this is important 100 00:05:31,250 --> 00:05:32,660 later on. Okay? 101 00:05:32,660 --> 00:05:36,259 Now, we do the same for x2 and we can reach five values now, zero, two, three 102 00:05:36,259 --> 00:05:40,046 and five. Or four values you know, zero, two, three 103 00:05:40,046 --> 00:05:43,060 and five. And then we do the same thing for x3. 104 00:05:43,060 --> 00:05:46,450 And then we reach many more values. And then we do the same for x4. 105 00:05:46,450 --> 00:05:49,310 And these are all the values that we can reach, all the combinations of zero and 106 00:05:49,310 --> 00:05:52,356 one. For x1, x2, x3, and x4, and that gives us 107 00:05:52,356 --> 00:05:56,360 the value which are basically between 0 and 12, except one. 108 00:05:56,360 --> 00:05:58,400 We can reach everything. Okay? 109 00:05:58,400 --> 00:06:00,360 So, that's basically the end of the forward phase. 110 00:06:00,360 --> 00:06:03,880 At this point, we have all these paths, which correspond to staking you know, 111 00:06:03,880 --> 00:06:08,852 some values for the variables and giving us a value for the sum at the end. 112 00:06:08,852 --> 00:06:10,853 Okay? Now the backward phase is going to, is 113 00:06:10,853 --> 00:06:13,110 going to start. And one of the things that we know is 114 00:06:13,110 --> 00:06:17,350 that this constraint to be feasible, we have to be between essentially 10 and 12. 115 00:06:17,350 --> 00:06:19,258 Okay? So all the other values which are at the 116 00:06:19,258 --> 00:06:22,866 bottom here, we really don't care. So we can get rid of them. 117 00:06:22,866 --> 00:06:24,849 Okay? And we can get rid of the, the, the nice 118 00:06:24,849 --> 00:06:28,314 arrows that were produced you know, because they are basically useless for 119 00:06:28,314 --> 00:06:31,294 us. They are not giving us feasible 120 00:06:31,294 --> 00:06:32,570 solutions. Okay? 121 00:06:32,570 --> 00:06:36,539 No, we did that for x4, we do that for x for x3 now, and then we do that for x2, 122 00:06:36,539 --> 00:06:40,603 and then now we have this beautiful graph. 123 00:06:40,603 --> 00:06:43,061 Okay? Where essentially these are describing 124 00:06:43,061 --> 00:06:46,715 the path that you can take for the various variables and therefore the 125 00:06:46,715 --> 00:06:50,747 combination of zero, and one for the various variable to arrive to a feasible 126 00:06:50,747 --> 00:06:53,657 solution. Okay? 127 00:06:53,657 --> 00:06:57,317 So we clean up the mess you know, such that we have only blue values for the 128 00:06:57,317 --> 00:07:03,486 the, the, the various unit transition states where for the various variables. 129 00:07:03,486 --> 00:07:07,386 And we've this beautiful things here, where we see some arrows going you know, 130 00:07:07,386 --> 00:07:11,406 some dash arrows, and some you know, solid arrows that in, in this particular 131 00:07:11,406 --> 00:07:13,858 graph. Okay? 132 00:07:13,858 --> 00:07:16,000 Now there is some thing beautiful to see now. 133 00:07:16,000 --> 00:07:17,946 Okay? So if you look at the variable like lets 134 00:07:17,946 --> 00:07:21,312 say x2 over there, you can see that there are two you know, solid lines and one 135 00:07:21,312 --> 00:07:25,098 dash line. What that basically means, is that, that 136 00:07:25,098 --> 00:07:27,440 variable can take value zero and the value one. 137 00:07:27,440 --> 00:07:29,592 Okay? Because the value, the dash line is value 138 00:07:29,592 --> 00:07:32,580 zero, the solid lines are value ones. Okay? 139 00:07:32,580 --> 00:07:35,060 Now, when you look at x4, that's very interesting. 140 00:07:35,060 --> 00:07:38,661 The only thing you see for x4 are basically solid lines. 141 00:07:38,661 --> 00:07:42,885 And you know, that basically means that value x4 cannot take the value zero and, 142 00:07:42,885 --> 00:07:47,050 and, and, and produce a feasible solution. 143 00:07:47,050 --> 00:07:50,460 And that is essential tells us that the values that the value 0 can be pruned 144 00:07:50,460 --> 00:07:54,370 from the domain of X4 and therefore X4 has to be one. 145 00:07:54,370 --> 00:07:58,466 If for one particle of variables all the, all the lines were dashed lines, you 146 00:07:58,466 --> 00:08:02,882 would know that that particular value should be, should be, that, that variable 147 00:08:02,882 --> 00:08:07,833 can take is 0 and not the value one. Okay? 148 00:08:07,833 --> 00:08:09,854 So now at this point, you know everything. 149 00:08:09,854 --> 00:08:11,631 Okay? You know how to prune and you know how to 150 00:08:11,631 --> 00:08:14,709 check feasibility. Feasibility is easy, you compute forward 151 00:08:14,709 --> 00:08:17,630 phrases, you see if you get into the feasible region. 152 00:08:17,630 --> 00:08:20,220 If you can't get into the feasible region, you are not feasible. 153 00:08:20,220 --> 00:08:23,433 And then essentially at the end, you prune, use the backwards phase or these 154 00:08:23,433 --> 00:08:26,517 dependencies. And then you look at every variable and 155 00:08:26,517 --> 00:08:29,730 see what kind of arrows you have, and that basically decides whether you can 156 00:08:29,730 --> 00:08:33,380 prune the value or not. Beautiful and simple, right? 157 00:08:34,660 --> 00:08:37,416 So, that was basically the Knapsack. What we are going to do now is to look at 158 00:08:37,416 --> 00:08:40,550 the alldifferent constraints, which is also very interesting. 159 00:08:40,550 --> 00:08:42,906 The algorithm is going to be based on graph theory. 160 00:08:42,906 --> 00:08:45,895 And this is another set, and this exemplifies essentially another set of 161 00:08:45,895 --> 00:08:49,180 constraints, heavily based on graph theory. 162 00:08:49,180 --> 00:08:50,945 Okay? So the feasibility here, once again, is 163 00:08:50,945 --> 00:08:53,735 going to be for every variable and every value, can I find, you know, values in 164 00:08:53,735 --> 00:08:56,570 the domain of the other variables such that all the variables get different 165 00:08:56,570 --> 00:08:59,580 values. Okay? 166 00:08:59,580 --> 00:09:01,932 And the pruning is that once again, you're going to look at a variable, 167 00:09:01,932 --> 00:09:04,242 you're going to look at the value, and then you're going to say, can that 168 00:09:04,242 --> 00:09:07,014 variable contain the value assuming that I have, you know, I can take values for 169 00:09:07,014 --> 00:09:10,780 the other variables. Okay? 170 00:09:10,780 --> 00:09:14,497 So, so this is for instance a, a simple illustration of, of the alldifferent 171 00:09:14,497 --> 00:09:17,662 constraints. You see the variable, you know x1, x2, 172 00:09:17,662 --> 00:09:21,820 x3, x4, and 5, and you see the domain of every one of these variables. 173 00:09:21,820 --> 00:09:23,650 Okay? They take different, they take different 174 00:09:23,650 --> 00:09:27,028 values in this particular case. Now, the kind of questions that we want 175 00:09:27,028 --> 00:09:30,430 to answer is you know, if the, if all these variables have to take a different 176 00:09:30,430 --> 00:09:35,076 values, can x4 take the value 2? Okay so look at this, can I find a 177 00:09:35,076 --> 00:09:38,797 solution to you know, assigning values in the domain to every one of these 178 00:09:38,797 --> 00:09:44,100 variables such that x4 takes the value 2. Okay? 179 00:09:44,100 --> 00:09:47,217 Now, that's not obvious, right? And you will see that essentially x4 180 00:09:47,217 --> 00:09:50,546 cannot take the value. There are no solution if you assign the 181 00:09:50,546 --> 00:09:53,324 value two to x4. And so the algorithm is going to find 182 00:09:53,324 --> 00:09:54,140 that. Okay? 183 00:09:54,140 --> 00:09:56,628 There are other values that you can remove here. 184 00:09:56,628 --> 00:09:59,028 You know, and this is a good question, can you find the values that you can 185 00:09:59,028 --> 00:10:01,070 remove here? Okay? 186 00:10:01,070 --> 00:10:04,398 Once again, what we want to do is find those values efficiently and remove them 187 00:10:04,398 --> 00:10:06,570 from the search page. Okay? 188 00:10:06,570 --> 00:10:09,010 So, to do that, we're going to to use a nice representation. 189 00:10:09,010 --> 00:10:11,830 You're going to see the valuables on the top, you're going to see the values on 190 00:10:11,830 --> 00:10:13,310 the bottom. Okay? 191 00:10:14,480 --> 00:10:17,910 And so, so in a sense we're going to have two kinds of notes. 192 00:10:17,910 --> 00:10:21,001 We're going to have the notes for the valuables and the notes for the values. 193 00:10:21,001 --> 00:10:22,522 Okay? So, these are the notes for the values, 194 00:10:22,522 --> 00:10:25,000 you see value 1, value 2, value 3, and so on. 195 00:10:25,000 --> 00:10:27,852 You see the set, and then essentially, if a variable can take a value, we are 196 00:10:27,852 --> 00:10:31,620 going to draw a match between the variables and the values. 197 00:10:31,620 --> 00:10:34,975 So, when you see x1 over there, x1 can take the value 1, x1 can take the value 198 00:10:34,975 --> 00:10:36,570 2. Okay? 199 00:10:36,570 --> 00:10:39,054 Now, you look, we look at val, variable two. 200 00:10:39,054 --> 00:10:42,470 You know, variable two can take value two and three, so we going to put an edge 201 00:10:42,470 --> 00:10:47,425 from x2 to 2 and an edge from x2 to 3. And we do that for all the variables. 202 00:10:47,425 --> 00:10:49,530 And then you get this beautiful graph, you know? 203 00:10:49,530 --> 00:10:52,275 Where there is an edge between the variable and the value, if essentially 204 00:10:52,275 --> 00:10:54,915 the value is in the domain of the variable. 205 00:10:54,915 --> 00:10:57,900 Okay? Note so far we hav you know we haven't 206 00:10:57,900 --> 00:11:00,690 done very much, except doing a very nice picture. 207 00:11:00,690 --> 00:11:03,044 Okay? And once again you know, with this 208 00:11:03,044 --> 00:11:07,712 representation, can you see that x4 cannot take the value 2. 209 00:11:07,712 --> 00:11:10,224 Okay? Now, so the first thing that we have to 210 00:11:10,224 --> 00:11:13,010 do is to find out if this constraint is feasible. 211 00:11:13,010 --> 00:11:14,550 Okay? That's always the first step. 212 00:11:14,550 --> 00:11:17,278 You know, we have the constraints, we have a set of domain for the variable, 213 00:11:17,278 --> 00:11:20,140 can we find a feasible solution. Okay? 214 00:11:20,140 --> 00:11:22,130 So, what you see here, this is a feasible solution. 215 00:11:22,130 --> 00:11:24,189 Okay? So you see that the variable x1 here is 216 00:11:24,189 --> 00:11:27,227 assigned a value of 1, you see that the variable x2 is assigned to the value 2 217 00:11:27,227 --> 00:11:30,894 and so on. What is nice here, is that you see these 218 00:11:30,894 --> 00:11:34,380 blue arrow representing the solutions. It's okay, blue arrows. 219 00:11:34,380 --> 00:11:37,370 This is, we're going to do that over and over again in this lecture. 220 00:11:37,370 --> 00:11:39,535 Okay? But essentially what we want is that 221 00:11:39,535 --> 00:11:43,990 every one of the variables on the top, you know, are assigned a blue edge. 222 00:11:43,990 --> 00:11:45,496 Okay? That means that they have assigned a 223 00:11:45,496 --> 00:11:47,360 value. And when you look at the values at the 224 00:11:47,360 --> 00:11:50,476 bottom, we want at most one of the blue arrows to come to them. 225 00:11:50,476 --> 00:11:53,271 Because if there would be two arrows, that basically means that two variables 226 00:11:53,271 --> 00:11:57,084 are assigned to the same value and therefore they are not different, right? 227 00:11:57,084 --> 00:11:58,821 Okay? So that's basically the idea. 228 00:11:58,821 --> 00:12:00,820 Okay? So it's going to be feasible if you have 229 00:12:00,820 --> 00:12:04,416 an arrow going from the top to the bottom and there is one going from, one you 230 00:12:04,416 --> 00:12:10,736 know, leaving every variable and at most one arriving tt every one of the values. 231 00:12:10,736 --> 00:12:12,850 Okay? So this is a feasible solution for 232 00:12:12,850 --> 00:12:14,230 instance. Okay? 233 00:12:14,230 --> 00:12:17,800 So what we did here was just creating a bipartite graph. 234 00:12:17,800 --> 00:12:21,895 And aloso a bipartite graph is a graph with two types of vertices, and edges are 235 00:12:21,895 --> 00:12:25,560 between vertices of different types. Okay? 236 00:12:25,560 --> 00:12:28,215 In the particular case of the all-different constraints, you have one 237 00:12:28,215 --> 00:12:31,442 type of vertices, the, the top ones which are the variables. 238 00:12:31,442 --> 00:12:34,038 And then we have the bottom ones which are the values and there is an edge 239 00:12:34,038 --> 00:12:36,590 between the variable, and the value if the value is in the domain of the 240 00:12:36,590 --> 00:12:39,640 variable. That's what we have done so far. 241 00:12:39,640 --> 00:12:41,585 Okay? So, in a sense you see that this is the 242 00:12:41,585 --> 00:12:45,050 first you know, set in the by product graph, that's the variable, you see the 243 00:12:45,050 --> 00:12:48,430 set of variables at the bottom. Okay? 244 00:12:48,430 --> 00:12:50,542 And once again you have an edge between the variable and value If that value is 245 00:12:50,542 --> 00:12:53,410 in the domain of the variable. Okay? 246 00:12:53,410 --> 00:12:57,770 Now, what we just did when I show you a solution was finding a matching. 247 00:12:57,770 --> 00:13:01,110 What is a matching? That's a basic concept in graph theory. 248 00:13:01,110 --> 00:13:04,582 And, if you have a graph, you know, with a set of vertices V, and a set of edges 249 00:13:04,582 --> 00:13:08,224 E, okay? So, matching is going to be a set of 250 00:13:08,224 --> 00:13:13,360 edge, E such that No two edge in E are sharing a vertex. 251 00:13:13,360 --> 00:13:15,481 Okay? So if you select an edge, you can never 252 00:13:15,481 --> 00:13:20,835 select another edge which is basically using one of the vertices of that edge. 253 00:13:20,835 --> 00:13:23,472 Okay? And then the maximum matching is going to 254 00:13:23,472 --> 00:13:26,685 be the matching where you have the large number, where you have selected the 255 00:13:26,685 --> 00:13:31,030 largest number of edges inside E. Okay? 256 00:13:31,030 --> 00:13:33,714 And so the constraint of course is as soon as you select an edge, you select 257 00:13:33,714 --> 00:13:37,410 two vertices and these vertices can not be selected any other edges. 258 00:13:37,410 --> 00:13:39,125 So you have to select these edges carefully. 259 00:13:39,125 --> 00:13:41,700 Okay? And so why is this interesting? 260 00:13:41,700 --> 00:13:45,586 Because essentially feasibility is the, the basically feasibility amounts to 261 00:13:45,586 --> 00:13:49,498 finding the maximum matching. If you find the maximum matching there 262 00:13:49,498 --> 00:13:53,081 are two cases right? One of the cases is that you know,the, 263 00:13:53,081 --> 00:13:56,680 the maximum matching is a size which is, you know, equal to the number of 264 00:13:56,680 --> 00:13:59,956 variables. That basically means that all the 265 00:13:59,956 --> 00:14:02,538 variables have been assigned. And by definition of the matching they 266 00:14:02,538 --> 00:14:04,506 are assigned a different value. Okay? 267 00:14:04,506 --> 00:14:07,440 And you know at that point that the constraint is feasible. 268 00:14:07,440 --> 00:14:10,464 If the maximum matching is smaller than the number of variables, okay, that 269 00:14:10,464 --> 00:14:13,630 basically means that there is no feasible solution. 270 00:14:13,630 --> 00:14:16,270 There is one or more variables that I cannot assign. 271 00:14:16,270 --> 00:14:20,007 I would have to assign a value which is already taken by another variable. 272 00:14:20,007 --> 00:14:22,680 Okay? So, in a sense, what I'm telling you is, 273 00:14:22,680 --> 00:14:27,818 feasibility here equals matching, okay? So, so now we have, basically, this is an 274 00:14:27,818 --> 00:14:28,830 example. Okay? 275 00:14:28,830 --> 00:14:31,410 So you see, you know, once again, the variable, the value at the top. 276 00:14:31,410 --> 00:14:34,570 You see these blue edges, beautiful. There is a, there is one edge leaving 277 00:14:34,570 --> 00:14:37,422 every variable. You know, most one edge arriving at every 278 00:14:37,422 --> 00:14:40,210 values and know that this constraint is feasible. 279 00:14:40,210 --> 00:14:44,430 This is another example, okay? So you see this is this is essentially, 280 00:14:44,430 --> 00:14:48,869 once again the valuable, the value, this is a different set of domains here. 281 00:14:48,869 --> 00:14:50,926 Okay? And I can try to find the maximum 282 00:14:50,926 --> 00:14:53,990 matching. And this is what I get. 283 00:14:53,990 --> 00:14:56,690 At this point, what you see is this matching is only five edges, and I have 284 00:14:56,690 --> 00:14:59,697 six variable. So, you know, that the constraint isn't 285 00:14:59,697 --> 00:15:00,740 feasible. Okay? 286 00:15:00,740 --> 00:15:04,185 So when you look at the variable X3 over there, you can see that I can't match any 287 00:15:04,185 --> 00:15:07,439 of these edges. I can use, I cannot use any of these 288 00:15:07,439 --> 00:15:10,581 edges because the values there are already taken. 289 00:15:10,581 --> 00:15:12,320 Okay? So essentially the maximum matching here 290 00:15:12,320 --> 00:15:15,565 is of size five, I have six variable, the constraint is not feasible. 291 00:15:15,565 --> 00:15:19,213 Okay, so essentially now I know that if I can find a maximum matching, I will be 292 00:15:19,213 --> 00:15:23,600 able to decide if the constraint is feasible or not. 293 00:15:23,600 --> 00:15:25,870 Okay? So how do I find this beautiful matching? 294 00:15:25,870 --> 00:15:27,494 Okay? So I start with any matching, and then 295 00:15:27,494 --> 00:15:29,496 I'm going to try to improve that. Okay? 296 00:15:29,496 --> 00:15:32,128 So and when no improvement is, is going to be possible, that basically 297 00:15:32,128 --> 00:15:36,460 means that I have a maximum matching. So it's a simple improvement algorithm. 298 00:15:36,460 --> 00:15:40,059 I start from any matching. Maybe a matching with nothing in it, and 299 00:15:40,059 --> 00:15:43,044 then I improve it. And when I'm stuck, I can't improve it, I 300 00:15:43,044 --> 00:15:46,890 know that I have a feasible matching. Of course, I haven't defined what it 301 00:15:46,890 --> 00:15:49,912 means to improve a matching, but I'm going to do that in the next slide. 302 00:15:49,912 --> 00:15:52,457 Okay? So, here, this is a, this is a matching. 303 00:15:52,457 --> 00:15:54,734 Okay? So you see that the variable x3, x4, x5, 304 00:15:54,734 --> 00:15:58,605 and x6 are basically matched. The variable x1 and x2 are not. 305 00:15:58,605 --> 00:16:00,631 Okay? So what I want to do now is improve this 306 00:16:00,631 --> 00:16:02,040 matching. Okay? 307 00:16:02,040 --> 00:16:09,515 So I can do, I can essentially, we place the edges x4, which is assigned to 2, and 308 00:16:09,515 --> 00:16:14,180 the edge x2 to 2. Okay? 309 00:16:14,180 --> 00:16:20,004 I can replace the x, sorry, I can replace the, the edge x4 to 2 by the x, the edges 310 00:16:20,004 --> 00:16:24,080 X2 to 2 and X4 to 4. Okay. 311 00:16:24,080 --> 00:16:27,120 If I do that, I remove one edge, and I have two new edges. 312 00:16:27,120 --> 00:16:29,470 Okay? And what I get is a better matching. 313 00:16:29,470 --> 00:16:32,270 Now five of the variables are matched. Okay. 314 00:16:32,270 --> 00:16:34,950 I can keep on improving this matching. Okay? 315 00:16:34,950 --> 00:16:42,506 I can essentially replace the the edge x3 as assigned to 1 by three new edges. 316 00:16:42,506 --> 00:16:45,292 Okay? actually I also ought to remove x5 to 3 317 00:16:45,292 --> 00:16:49,324 and I replace them by (x1,1), (X3,3) and (x5, 5). 318 00:16:49,324 --> 00:16:51,453 Okay? So I remove two edges and I replace them 319 00:16:51,453 --> 00:16:54,960 by three new ones. And then I get this beautiful matching 320 00:16:54,960 --> 00:16:58,160 [UNKNOWN], where essentially all the variables are matched. 321 00:16:58,160 --> 00:17:02,260 I have a maximum matching, and I will know that this constraint is feasible. 322 00:17:02,260 --> 00:17:05,236 So what I basically did was always selecting one edge and replacing by two, 323 00:17:05,236 --> 00:17:08,190 or selecting two edges and replacing by three. 324 00:17:08,190 --> 00:17:10,760 And that's how I improve the matching. Okay? 325 00:17:10,760 --> 00:17:14,351 Now, this is not precise enough, and I'm going to go into more details now. 326 00:17:14,351 --> 00:17:16,010 Okay? So once again, what we're going to do, 327 00:17:16,010 --> 00:17:18,120 start with a matching, improve the matching. 328 00:17:18,120 --> 00:17:19,932 How do we improve a matching? Okay? 329 00:17:19,932 --> 00:17:23,452 So what we will do is find a free vertex, and that will be in the particular case 330 00:17:23,452 --> 00:17:28,368 of the all-different, finding a variable which is not assigned a value. 331 00:17:28,368 --> 00:17:30,559 Okay? And now there are two cases. 332 00:17:30,559 --> 00:17:32,660 Okay? The first case is, is the case where I 333 00:17:32,660 --> 00:17:36,635 can find a value, which is unmatched. That basically means that that value is 334 00:17:36,635 --> 00:17:39,100 free, no other variable is assigned to that value. 335 00:17:39,100 --> 00:17:41,980 If I can do that, obviously I can improve the matching. 336 00:17:41,980 --> 00:17:43,904 Okay? And I can put that edge in the matching, 337 00:17:43,904 --> 00:17:47,780 and then start again trying to continue improving that matching. 338 00:17:47,780 --> 00:17:50,840 Now, the more interesting case is when that variable you know, cannot be 339 00:17:50,840 --> 00:17:55,500 assigned to any other values at this point because all these values are taken. 340 00:17:55,500 --> 00:17:57,600 Okay? So what I do in that case is that I take 341 00:17:57,600 --> 00:18:00,792 that value, I assign it to the particular variable. 342 00:18:00,792 --> 00:18:03,648 Now I take the variable which is currently assigned to that value, I 343 00:18:03,648 --> 00:18:08,055 remove the edge between them, and then I start again with that variable. 344 00:18:08,055 --> 00:18:10,389 Okay? And I try to find you know, an assignment 345 00:18:10,389 --> 00:18:14,171 for that variable to a value in the same way as I did for the origin of free 346 00:18:14,171 --> 00:18:17,370 variable. Okay? 347 00:18:17,370 --> 00:18:18,790 Let me illustrate that. Okay? 348 00:18:18,790 --> 00:18:22,262 So we've once again this beautiful matching, we've only you know you know, 349 00:18:22,262 --> 00:18:25,270 variables assigned. Okay? 350 00:18:25,270 --> 00:18:31,030 I'm trying to see how I can improve it. So, I select the variable x2 which is 351 00:18:31,030 --> 00:18:33,710 free, and the value 2. Okay? 352 00:18:33,710 --> 00:18:36,350 So, this is what you see there. You see the variable x2 is free. 353 00:18:36,350 --> 00:18:39,085 No, no, no value, it has no value assigned to it. 354 00:18:39,085 --> 00:18:43,549 I take the value 2, but the value two you can see is assigned to the var, to the 355 00:18:43,549 --> 00:18:47,685 variable x4. Therefore, what I have to do is 356 00:18:47,685 --> 00:18:51,020 essentially remove the edge between x4 and 2. 357 00:18:51,020 --> 00:18:55,592 Okay? And start again with the variable x4. 358 00:18:55,592 --> 00:18:59,102 Okay? So I remove x2 to 2. 359 00:18:59,102 --> 00:19:02,112 Okay? And then I consider variable x4 at this 360 00:19:02,112 --> 00:19:03,496 point. Okay? 361 00:19:03,496 --> 00:19:08,546 And, so I start again, so you see the variable x4 now is free. 362 00:19:08,546 --> 00:19:11,305 Okay? And I look, if I can find a value for 363 00:19:11,305 --> 00:19:15,060 that particular variable. Okay? 364 00:19:15,060 --> 00:19:17,844 Such that I can improve the matching. Okay? 365 00:19:17,844 --> 00:19:21,936 What is nice in this particular case, is that I can assign the value X4 to the 366 00:19:21,936 --> 00:19:24,260 value 4. Okay? 367 00:19:24,260 --> 00:19:28,576 And therefore I even improve matching. So, what I did was essentially adding two 368 00:19:28,576 --> 00:19:32,996 edges, one from x2 to x to 2, and one from x4 to 4. 369 00:19:32,996 --> 00:19:37,205 And I remove only one edge, the edge x4 to 2, which is basic, which was in the 370 00:19:37,205 --> 00:19:40,960 matching before. So I remove one edge from the matching, I 371 00:19:40,960 --> 00:19:43,607 have added two new edge which were not in the matching. 372 00:19:43,607 --> 00:19:45,840 So I improve my matching. Okay? 373 00:19:45,840 --> 00:19:48,666 So, that's the basic idea. So essentially what I'm using here is 374 00:19:48,666 --> 00:19:50,830 what is called an alternating path. Okay? 375 00:19:50,830 --> 00:19:55,366 So, if I have a matching, an alternating path from a free vertex in x, you know 376 00:19:55,366 --> 00:19:59,758 the top set of, the top of vertices, to a vi, to a vi, to a vertex in v okay, as a 377 00:19:59,758 --> 00:20:05,605 set of value. It's going to be a path, you know, 378 00:20:05,605 --> 00:20:09,125 essentially, from, from this variable x to the variable v, where the edge are 379 00:20:09,125 --> 00:20:14,970 going to alternate between being not in the matching and being in the matching. 380 00:20:14,970 --> 00:20:17,421 So I'm going to start from x, take an edge which is not in the matching, go 381 00:20:17,421 --> 00:20:20,087 back to the top of an edge, which is in the matching, and go to the bottom with 382 00:20:20,087 --> 00:20:24,290 an edge, which is not in the matching, and so on. 383 00:20:24,290 --> 00:20:27,865 Okay? Until I fin, I can assign that particle 384 00:20:27,865 --> 00:20:32,860 of variable to a value which is not taken by any other vertices. 385 00:20:32,860 --> 00:20:34,422 Okay? Now, there is an odd number of edges 386 00:20:34,422 --> 00:20:36,676 here, why? Because I start from the top and I end up 387 00:20:36,676 --> 00:20:38,490 at the bottom. Okay? 388 00:20:38,490 --> 00:20:41,120 So to go from the top to the bottom, you know I need one edge. 389 00:20:41,120 --> 00:20:43,880 Every time I go up and down, this is an even number of edges. 390 00:20:43,880 --> 00:20:46,520 So we're basically I will have an odd number of edges. 391 00:20:46,520 --> 00:20:49,847 And this is really important, right? Because if I have an odd number of edges, 392 00:20:49,847 --> 00:20:53,032 and I always start by taking something which is not in the matching, I know that 393 00:20:53,032 --> 00:20:58,015 I will increase you know, the number of edge inside the matching by one. 394 00:20:58,015 --> 00:21:00,614 Okay? So I'm improving essentially the 395 00:21:00,614 --> 00:21:01,730 matching. Okay? 396 00:21:01,730 --> 00:21:05,264 I remove let's say k edge region area inside the matching and I add, k mine, k 397 00:21:05,264 --> 00:21:09,796 plus 1 edges, which are not in the match. Really good. 398 00:21:09,796 --> 00:21:12,030 Okay? So these alternating paths essentially, 399 00:21:12,030 --> 00:21:15,660 are allowing me to improve the matching. Okay? 400 00:21:15,660 --> 00:21:19,586 So, how do I find this alternating path? You can see I'm basically moving step by 401 00:21:19,586 --> 00:21:22,200 step, refining this concept one at a time. 402 00:21:22,200 --> 00:21:25,842 And this is the final step, okay? So, I'm basically telling you what the 403 00:21:25,842 --> 00:21:29,043 algorithm is. You have to create a directed graph. 404 00:21:29,043 --> 00:21:30,908 Okay? given a particular matching. 405 00:21:30,908 --> 00:21:32,783 Okay? Now, the edge of the matching are 406 00:21:32,783 --> 00:21:36,425 going to be oriented top to, from the bottom to the top. 407 00:21:36,425 --> 00:21:38,706 Okay? So these edges are going to allow me to 408 00:21:38,706 --> 00:21:41,357 go to the top. And the edges which are not in the 409 00:21:41,357 --> 00:21:44,930 matching are going to be oriented from the top to the bottom. 410 00:21:44,930 --> 00:21:48,811 I'm basically, we'll be able to assign a value to a particular variable. 411 00:21:48,811 --> 00:21:50,644 Okay? So this is essentially the illustration 412 00:21:50,644 --> 00:21:54,140 for the examples that you've seen. So, you see these blue edges now, you 413 00:21:54,140 --> 00:21:56,790 know, they are oriented to the top. Okay? 414 00:21:56,790 --> 00:22:00,040 And the other edges, the edges which are not in the matching, are oriented from 415 00:22:00,040 --> 00:22:03,990 the top to the bottom. Now I have a derivative graph, right? 416 00:22:03,990 --> 00:22:07,462 And remember, what I want to do is to find a path from a free vertex to another 417 00:22:07,462 --> 00:22:11,670 free vertex, on the top, to a free vertex at the bottom. 418 00:22:11,670 --> 00:22:14,121 So when I'm going to go down, I have to take an edge which is going down and 419 00:22:14,121 --> 00:22:17,280 those edges are basically not in the matching. 420 00:22:17,280 --> 00:22:20,390 And then I can only go up with up with edges which are in the matching. 421 00:22:20,390 --> 00:22:22,870 So I'm going to down, up, down, up. You know? 422 00:22:22,870 --> 00:22:25,650 Not in the matching, in the matching, not in the matching, in the matching. 423 00:22:25,650 --> 00:22:28,086 And now I can follow the direction of these edges. 424 00:22:28,086 --> 00:22:30,648 Okay? So essentially, this is, this is what I 425 00:22:30,648 --> 00:22:31,890 have done. Okay? 426 00:22:31,890 --> 00:22:34,950 So I create a directed graph, I take the edges which are in the matching, I 427 00:22:34,950 --> 00:22:38,060 re-orient it from the bottom to the top. Okay? 428 00:22:38,060 --> 00:22:40,890 And the other edges are oriented from the top to the bottom. 429 00:22:40,890 --> 00:22:44,465 And now essentially an alternating path ,is starting at the top and following 430 00:22:44,465 --> 00:22:48,930 these oriented edges until it reaches a free vertex at the bottom. 431 00:22:48,930 --> 00:22:51,180 Okay? I start at the top in a free vertex. 432 00:22:51,180 --> 00:22:54,999 I'm following these directed edges until I reach a free vertex at the bottom, and 433 00:22:54,999 --> 00:22:57,074 then I'm happy. Okay? 434 00:22:57,074 --> 00:23:01,020 I can find an alternating path, and therefore I can improve my matching. 435 00:23:01,020 --> 00:23:02,840 Okay? so look at this. 436 00:23:02,840 --> 00:23:05,118 Okay? So this again a beautiful graph oriented, 437 00:23:05,118 --> 00:23:10,020 and then I'm basically highlighting the vertex which are free at this point. 438 00:23:10,020 --> 00:23:14,168 You can see that x1 and x2 are free at the level of the values you have 4, 5 and 439 00:23:14,168 --> 00:23:17,370 7, which are free. Okay? 440 00:23:17,370 --> 00:23:20,045 So what do I do? I start from something which is free and 441 00:23:20,045 --> 00:23:22,880 then I try to see, to follow a path until I get to something which is free at the 442 00:23:22,880 --> 00:23:25,000 bottom. Okay? 443 00:23:25,000 --> 00:23:27,470 So I, so this is one of these beautiful path. 444 00:23:27,470 --> 00:23:30,470 Right? So you start from x2, you go to value 3 445 00:23:30,470 --> 00:23:37,270 and then you go up to variable x5 and then you go down to to value 4. 446 00:23:37,270 --> 00:23:39,242 Okay? So once again it's nice, you know, you 447 00:23:39,242 --> 00:23:41,804 start at the top, you, you go to the bottom, with and edge which is not in the 448 00:23:41,804 --> 00:23:44,450 matching, take an edge which is in the matching to go back up, and then go down 449 00:23:44,450 --> 00:23:48,060 again. Okay? 450 00:23:48,060 --> 00:23:50,832 And though, I can't replace these things by the edges which are in the matching, 451 00:23:50,832 --> 00:23:54,195 are going up, the edges are not in the matching are going down. 452 00:23:54,195 --> 00:23:56,965 Okay. And now I have one more variable which 453 00:23:56,965 --> 00:24:00,430 has been assigned, and I have only one free variable here which is the little 454 00:24:00,430 --> 00:24:03,370 x1, which is left alone. Okay. 455 00:24:03,370 --> 00:24:06,762 So now what I do, is I look at this guy, I try to find another an alternating path 456 00:24:06,762 --> 00:24:09,809 for x1. And you're going to see it's a beautiful 457 00:24:09,809 --> 00:24:13,360 path juju going up and down, until it reaches the value 5. 458 00:24:13,360 --> 00:24:15,236 Okay? Once again, you know the edges, the edges 459 00:24:15,236 --> 00:24:18,008 which were going down are going to go up, the edges which were going up are going 460 00:24:18,008 --> 00:24:21,076 to go down and this is my graph at the end. 461 00:24:21,076 --> 00:24:22,994 Okay? And now x1 has been assigned, all the 462 00:24:22,994 --> 00:24:26,945 values at the top now are assigned and almost all the values are assigned. 463 00:24:26,945 --> 00:24:29,859 But we don't really care about the values, because we really care about the 464 00:24:29,859 --> 00:24:33,605 variables and, and be sure they are assigned different values. 465 00:24:33,605 --> 00:24:35,545 Okay? And at this point of course, I have a 466 00:24:35,545 --> 00:24:40,038 feasible solution and this is the matching, essentially that I have. 467 00:24:40,038 --> 00:24:41,999 Okay? So this is essentially what I do. 468 00:24:41,999 --> 00:24:44,298 Okay? So for finding the alternating path. 469 00:24:44,298 --> 00:24:46,206 Okay? I'm basically going from top to the 470 00:24:46,206 --> 00:24:51,480 bottom and until I get to a free vertex at the bottom, which is a free values. 471 00:24:51,480 --> 00:24:53,890 And essentially what I do is I do that interactively. 472 00:24:53,890 --> 00:24:56,340 I take a variable, [SOUND] I look for the spot. 473 00:24:56,340 --> 00:24:58,540 If I can improve, great, I have a better matching. 474 00:24:58,540 --> 00:25:01,040 I take another one, [SOUND] I do the same thing. 475 00:25:01,040 --> 00:25:02,520 Okay? How do I find this path? 476 00:25:02,520 --> 00:25:05,622 I can use traditional depth-first search or best-first search to do that, and I 477 00:25:05,622 --> 00:25:08,595 get a very low polynomial algorithm to do that. 478 00:25:08,595 --> 00:25:10,380 Okay? So this is beautiful because now, 479 00:25:10,380 --> 00:25:14,870 essentially I know how to find a maximum matching, it's a very simple thing. 480 00:25:14,870 --> 00:25:16,942 Okay? You just have to re-orient the graph, you 481 00:25:16,942 --> 00:25:20,334 have just to construct this bipartite graph, or enter it in the right way, and 482 00:25:20,334 --> 00:25:23,461 search for the, for the, for the alternating path inside this directed 483 00:25:23,461 --> 00:25:27,370 graph. So, to summarize, what we do is we build 484 00:25:27,370 --> 00:25:31,305 this bipartite graph, we have a vertex set for the variable on top. 485 00:25:31,305 --> 00:25:33,644 Okay? We have a set of, we have another set of 486 00:25:33,644 --> 00:25:36,938 variable, set of vertices for the values of the bottom, and we have an edge 487 00:25:36,938 --> 00:25:42,518 between a variable and a value if that value's in the domain of the variable. 488 00:25:42,518 --> 00:25:44,829 Okay? Then, essentially, the feasibility. 489 00:25:44,829 --> 00:25:46,145 Okay? So the constraints is going to be 490 00:25:46,145 --> 00:25:48,520 feasible. If we have a maximum matching, which 491 00:25:48,520 --> 00:25:51,484 whose values is the same as the number of variables. 492 00:25:51,484 --> 00:25:54,620 And to do that, the only thing that we have to do is find this alternating path, 493 00:25:54,620 --> 00:25:57,511 which are going to improve the matching one step at a time, until we get the 494 00:25:57,511 --> 00:26:01,548 maximum matching. And when we have it, we just compare it 495 00:26:01,548 --> 00:26:03,130 to the number of variables. Okay? 496 00:26:03,130 --> 00:26:06,395 So we have done part one, which is essentially finding feasibility. 497 00:26:06,395 --> 00:26:08,420 Okay? Now, we have to prune now. 498 00:26:08,420 --> 00:26:11,759 What does it mean to prune is that, if a variable x can take a value v, we have to 499 00:26:11,759 --> 00:26:16,390 see if that particular variable, you know, belongs to a solution. 500 00:26:16,390 --> 00:26:19,735 That means that we can find values for the domain of the other variables. 501 00:26:19,735 --> 00:26:21,407 Okay? Such that, you know, all the variables 502 00:26:21,407 --> 00:26:23,960 are given different values. Okay? 503 00:26:23,960 --> 00:26:27,800 Now, if we translate that in the context of the matching, what it means is that 504 00:26:27,800 --> 00:26:31,109 this edge belong to some matching. Okay? 505 00:26:31,109 --> 00:26:36,160 So there is a very easy algorithm and very naive algorithm to do that. 506 00:26:36,160 --> 00:26:38,541 You basically force this edge in the matching. 507 00:26:38,541 --> 00:26:40,123 Okay? So if we have, we're looking at x, 508 00:26:40,123 --> 00:26:43,308 variable x and value v, we're basically removing all the other parts that have 509 00:26:43,308 --> 00:26:46,892 value for variable x. So if w is a value, remove the edge, 510 00:26:46,892 --> 00:26:49,799 there is only one edge which is left for x. 511 00:26:49,799 --> 00:26:52,760 So if we're finding a maximum matching you know, x will be forced to take this 512 00:26:52,760 --> 00:26:55,720 value v. And then we look if we can you know, find 513 00:26:55,720 --> 00:27:00,060 a maximum match whose values is essentially the number of variables. 514 00:27:00,060 --> 00:27:03,044 If we can do that, we are fine. Now, the problem with this of course, is 515 00:27:03,044 --> 00:27:06,820 that we have to take all these edges and then find a maximum matching. 516 00:27:06,820 --> 00:27:10,620 Take another edge, find another matching, a matching, so it's really tiring. 517 00:27:10,620 --> 00:27:12,200 It takes a lot of time. Okay? 518 00:27:12,200 --> 00:27:15,154 So we can do better. And there is this basic property, crazy 519 00:27:15,154 --> 00:27:19,820 property by Berge, in 1970, which was found by [UNKNOWN]. 520 00:27:19,820 --> 00:27:23,168 And so what is interesting here is that this property seems to come out of no 521 00:27:23,168 --> 00:27:24,660 where. Okay? 522 00:27:24,660 --> 00:27:27,380 But I'm going to read it to you and, and tell you why it's relevant. 523 00:27:27,380 --> 00:27:29,604 Okay? Basically this property is basically 524 00:27:29,604 --> 00:27:33,264 saying that an edge belong to some, but not all, okay, some, not all, okay, 525 00:27:33,264 --> 00:27:37,579 matching. If given a maximum matching, it belongs 526 00:27:37,579 --> 00:27:39,644 to other two things. Okay? 527 00:27:39,644 --> 00:27:41,645 An even alternating cycle. Okay? 528 00:27:41,645 --> 00:27:45,971 So that's a cycle which has length or or length which is even. 529 00:27:45,971 --> 00:27:48,509 Okay? Or an even alternating path which starts 530 00:27:48,509 --> 00:27:51,330 at a free vertex. Okay? 531 00:27:51,330 --> 00:27:53,060 So it's crazy, right? This property is crazy. 532 00:27:53,060 --> 00:27:55,292 First, you know, we are looking at some but not all the matching, and then we 533 00:27:55,292 --> 00:27:57,490 have these two, you know, crazy properties. 534 00:27:57,490 --> 00:28:01,476 But why is it so relevant to us? Well, you know, the edges in the 535 00:28:01,476 --> 00:28:04,060 matching, we really don't care about that, right? 536 00:28:04,060 --> 00:28:06,370 Because we know they are in the matching, so we know we can't remove them from the 537 00:28:06,370 --> 00:28:09,995 domain of the variables. So what we are really looking at here, 538 00:28:09,995 --> 00:28:13,660 are edges which are not in the matching. So we know that in the best case, they 539 00:28:13,660 --> 00:28:16,710 belong to some matching but they won't be long to all. 540 00:28:16,710 --> 00:28:18,750 And this is what really this property is about. 541 00:28:18,750 --> 00:28:21,391 So this is like magic, right? So this is just the property that we 542 00:28:21,391 --> 00:28:23,356 need. So the only thing that we have to do, is 543 00:28:23,356 --> 00:28:27,900 for all these edges which we are not in matching, we have to look at two things. 544 00:28:27,900 --> 00:28:31,776 Do they belong to even alternating cycle, or do they belong to an even alternating 545 00:28:31,776 --> 00:28:35,061 path which starts with a free vertex? Okay? 546 00:28:35,061 --> 00:28:38,416 So essentially this property is telling us really what we want to do, and it 547 00:28:38,416 --> 00:28:42,126 basically boils down to looking at these two things. 548 00:28:42,126 --> 00:28:44,219 Okay? Which is much easier essentially, than 549 00:28:44,219 --> 00:28:47,300 looking at all of the things we had to do before. 550 00:28:47,300 --> 00:28:49,650 So what are the free vertices in this particular case? 551 00:28:49,650 --> 00:28:54,190 The free vertices are of, where are they? Are they the variables or the values? 552 00:28:54,190 --> 00:28:56,373 Well, we know that the constraint is feasible, so all the variables are 553 00:28:56,373 --> 00:28:59,126 matched. So the only you know, free vertices are 554 00:28:59,126 --> 00:29:02,400 really the values. And that's where we're going to start, 555 00:29:02,400 --> 00:29:05,575 essentially, when we search for this even alternating path. 556 00:29:05,575 --> 00:29:07,419 Okay? So essentially what we're going to do is 557 00:29:07,419 --> 00:29:11,310 the same thing as is for feasibility, except that it's the opposite. 558 00:29:11,310 --> 00:29:13,236 Okay? So we create a directed graph, but this 559 00:29:13,236 --> 00:29:16,600 time around the edges are oriented in the different way. 560 00:29:16,600 --> 00:29:19,590 Why, because before we were looking to assign the variables. 561 00:29:19,590 --> 00:29:21,990 Here we are going to look at alternating pump that are starting at the three 562 00:29:21,990 --> 00:29:24,390 vertices, and these guys are the values now. 563 00:29:24,390 --> 00:29:26,542 Okay? So we start at the bottom and then we can 564 00:29:26,542 --> 00:29:29,880 go up, if the edges don't belong to the matching. 565 00:29:29,880 --> 00:29:33,520 And, and edges belong to the matching go from top to the bottom. 566 00:29:33,520 --> 00:29:36,420 Okay? So this is, once again, an illustration. 567 00:29:36,420 --> 00:29:39,129 It's essentially the same thing as we have seen before, except the edges are 568 00:29:39,129 --> 00:29:42,306 the other re-direction. So you see this guy here, this seven, 569 00:29:42,306 --> 00:29:44,283 this is a free variable. Okay? 570 00:29:44,283 --> 00:29:45,621 This is a free value. Okay? 571 00:29:45,621 --> 00:29:48,488 And then it can go up you know, to some of the variables and then the edges in 572 00:29:48,488 --> 00:29:52,570 the matching, the blue edges are going from top to the bottom down. 573 00:29:53,620 --> 00:29:56,110 So, remember we need to do two, we need to do a couple of things. 574 00:29:56,110 --> 00:29:58,518 We have to find the even alternating path. 575 00:29:58,518 --> 00:30:00,410 Okay? Starting at the free vertex. 576 00:30:00,410 --> 00:30:02,800 We have only one free vertex in this particular case. 577 00:30:02,800 --> 00:30:05,487 And then we have to find the even alternating cycle. 578 00:30:05,487 --> 00:30:07,433 Okay? So we are going to do that. 579 00:30:07,433 --> 00:30:09,120 Okay? One step at a time. 580 00:30:09,120 --> 00:30:12,099 this is, this, I'm using this graph. So the first thing we are going to do is 581 00:30:12,099 --> 00:30:16,072 to start from the even alternating path, starting from free vertex p. 582 00:30:16,072 --> 00:30:18,086 Okay? So we have this beautiful seven here. 583 00:30:18,086 --> 00:30:18,989 Okay? It's free. 584 00:30:18,989 --> 00:30:21,002 Okay? And then we are looking for an even 585 00:30:21,002 --> 00:30:22,845 alternating path. Okay? 586 00:30:22,845 --> 00:30:26,385 And we can take it as long as we can, because the, the longer it is the more 587 00:30:26,385 --> 00:30:30,919 values we know don't you know, can not be removed. 588 00:30:30,919 --> 00:30:35,010 So in this particular case we see this beautiful path [SOUND]. 589 00:30:35,010 --> 00:30:40,670 All these values here, we know that they belong to some but not all the matching. 590 00:30:40,670 --> 00:30:41,447 Okay? Great! 591 00:30:41,447 --> 00:30:43,655 Okay? So, we can remove these, well, we can, we 592 00:30:43,655 --> 00:30:47,320 can make them dash, which basically means that please don't remove them. 593 00:30:47,320 --> 00:30:50,466 We know that they can't be removed. They belong to some matching. 594 00:30:50,466 --> 00:30:51,745 Okay? So, that's the first step. 595 00:30:51,745 --> 00:30:54,728 Okay? And then second step now is going to be 596 00:30:54,728 --> 00:30:58,730 looking at things that belong to even alternating cycle. 597 00:30:58,730 --> 00:31:01,590 How do we do that, well there's this beautiful algorithm, which is which is 598 00:31:01,590 --> 00:31:04,450 called you know, finding strongly connected components, which does exactly 599 00:31:04,450 --> 00:31:07,830 that. These strongly collected component are 600 00:31:07,830 --> 00:31:11,030 basically component which can all reach you know, move there is apart to move 601 00:31:11,030 --> 00:31:13,830 from one to the other, to, to all the other ones in the same connected 602 00:31:13,830 --> 00:31:17,590 component. So to do this now, the only thing that 603 00:31:17,590 --> 00:31:20,340 you have to do is to loop this algorithm. Okay? 604 00:31:20,340 --> 00:31:23,859 Which was defined long time ago using depth for search by [UNKNOWN]. 605 00:31:23,859 --> 00:31:27,239 And then once you basically you know, run this algorithm, you will find all the 606 00:31:27,239 --> 00:31:29,492 even alternating cycle. Okay? 607 00:31:29,492 --> 00:31:32,564 So in this particular case, look at this one, this is a beautiful alternating 608 00:31:32,564 --> 00:31:35,650 cycle. We start from x1, and then we go down, go 609 00:31:35,650 --> 00:31:39,335 to x2, go to x3, and go back to x1 afterwards. 610 00:31:39,335 --> 00:31:41,665 Okay? So, essentially all these edges belong to 611 00:31:41,665 --> 00:31:44,260 an even alternating cycle. They belong to [INAUDIBLE] connected 612 00:31:44,260 --> 00:31:46,110 component. We can't touch these edges. 613 00:31:46,110 --> 00:31:47,990 They belong to some matching. Okay? 614 00:31:47,990 --> 00:31:51,224 And at this point, the only thing that is left is all the edges which belong to the 615 00:31:51,224 --> 00:31:54,240 original matching that we have found. Okay? 616 00:31:54,240 --> 00:31:56,600 Those were the blue edges that we have seen before. 617 00:31:56,600 --> 00:31:59,440 And now everything else can be removed. Okay? 618 00:31:59,440 --> 00:32:03,304 So, in part, in this particular case, you see. 619 00:32:03,304 --> 00:32:05,948 Okay? So this beautiful value 2, (2, x4 ) that 620 00:32:05,948 --> 00:32:11,892 we discussed at the beginning of the lecture, we know that we can remove it. 621 00:32:11,892 --> 00:32:14,220 Okay? And so you can remove all the edges which 622 00:32:14,220 --> 00:32:18,180 don't belong to the even alternating path, starting from the free vertex to 623 00:32:18,180 --> 00:32:22,430 even alternating cycles, and then the matching. 624 00:32:22,430 --> 00:32:25,725 Okay? So you can remove this x4 to 2 and remove 625 00:32:25,725 --> 00:32:30,453 x5 to 3 and x5 to 4. And to now, essentially that this is the 626 00:32:30,453 --> 00:32:34,235 pruned graph, after we have removed all the values that don't belong to any 627 00:32:34,235 --> 00:32:36,524 matching. Okay? 628 00:32:36,524 --> 00:32:39,944 So essentially the complexity here, once again is going to be a nice low 629 00:32:39,944 --> 00:32:43,847 polynomial logarithm. You don't have to try all these, these 630 00:32:43,847 --> 00:32:47,570 particular edges and run a matching algorithm on them. 631 00:32:47,570 --> 00:32:50,170 It's much more efficient. Okay? 632 00:32:50,170 --> 00:32:54,074 And at this point you know how to do feasibility and pruning for up, for all 633 00:32:54,074 --> 00:32:57,716 different constraints. So what we've seen in this lecture are 634 00:32:57,716 --> 00:33:00,460 two things. We saw two different algorithm. 635 00:33:00,460 --> 00:33:02,318 Okay? For you know, finding feasibility and 636 00:33:02,318 --> 00:33:05,770 pruning of normal constraints. One of them was a knapsack. 637 00:33:05,770 --> 00:33:09,117 We use a dynamic programming algorithm. The other one was an all-different 638 00:33:09,117 --> 00:33:12,619 constraint, which was basically using a matching algorithm. 639 00:33:12,619 --> 00:33:14,615 Okay? And some you know, graph algorithm for 640 00:33:14,615 --> 00:33:17,602 strongly connected components and finding paths. 641 00:33:17,602 --> 00:33:19,475 Okay? And that basically illustrates you know, 642 00:33:19,475 --> 00:33:23,396 the whole purpose of global constraint. For every one of these constraints, we 643 00:33:23,396 --> 00:33:27,382 can use a dedicated algorithm. You know, exploiting the particular 644 00:33:27,382 --> 00:33:31,152 structure of that constraint, and the whole area of global constraint is just 645 00:33:31,152 --> 00:33:34,881 about that. Finding the best possible algorithm for 646 00:33:34,881 --> 00:33:38,535 feasibility and pruning exploiting as much of the structure as we can okay, 647 00:33:38,535 --> 00:33:42,110 that's it for today, thank you very much.