0:00

Okay, this is discrete optimization constraint programming part two.

Â Okay, so this is the goal of the lectures, of the lecture.

Â Okay, so we're going to illustrate more complex constraint propagation.

Â And the underlying topic is the fact that every one of the constraints in a

Â constraint programming system has a dedicated algorithm, okay?

Â So that's, so basically, that's the technical part, okay?

Â So what are we going to do from a non technical standpoint, is that, for the

Â first time, you're going to see a complex propagation algorithm if you have never

Â seen any. And it's kind of amazing how, how these

Â things are working. The kind of information that you are

Â deducing. It's, like, you know, the first time you

Â see this, it's like, wow, this program is actually pretty bright, okay?

Â Of course, it's not, but, anyway, so it's going to give you a sense of what a

Â constraint propagation algorithm is doing.

Â It's kind of interesting. Okay, so remember, in constraint

Â programming is this combination of branch and prune.

Â Pruning is removing value from the domain of the variables in a first

Â approximation. Branching is, oh, you're stuck.

Â There is no propagation. You decide whether, you know, you assign

Â a value. You decide to split the problems into

Â sub-problems. Typically, you take a values and you

Â start giving all kinds of values for it. You know, in turn.

Â Okay? and then obviously, you know, once you

Â branch you apply the constraint propagation algorithm to prune the search

Â space again. Now, pruning is basically, as I told you,

Â you are using the constraints while, you know, removing as many values from the

Â domain of as many variables as possible. Okay?

Â Branching is, you know, in, in our first approximation we'll see most

Â sophisticated branches came later on, later on, but essentially trying

Â possible, you know, trying possible values for the variables.

Â Okay? Remember with this beautiful separation

Â between the search engine and the, the constraint, the constraint store.

Â Okay? And so what is happening is this guy is

Â basically trying to see if the constraint is satisfiable.

Â And when it, when it tries to derive as much information as it can.

Â The search will make a choice and send a new constraint.

Â And the constraint store is to be able to say yes or no.

Â Okay? Am I still feasible, okay, or not?

Â Am I infeasible, or am I infeasible, okay?

Â And if it's feasible, if you believe it's feasible, you're going to say yeah, it's

Â fine, you know, as far as I can tell I'm feasible.

Â And sometimes, you know, you add a new constraint and then the system will say

Â oh, no, no, I'm infeasble. You know, remove that choice, give me

Â another choice. Okay.

Â So that's basically the essence of, of constraint programming.

Â The inside of this constraint store is very interesting.

Â All right. So you have the domain store here, which

Â is basically capturing the search space, typically associated domains to every one

Â of the variables. And then gravitating around it are the,

Â all these constraints. Okay?

Â And they don't know about each other, and that's the key point.

Â Okay? And these constraints have two goals in

Â life. I told you they basically are asking

Â themselves, oh, am I feasible with respect to this field of, of domains?

Â So can I find an assignment for the variables using these domains such that,

Â you know, I'm, you know, this constraint is satisfied?

Â And then they will say, oh, but can I actually knock down some values in these

Â domains, such that I reduce the search space, okay.

Â And of course, as soon as you do that, some of the constraints may become

Â infeasible, or some of the constraints may be able to knock down more values

Â from these domains. And that's the constraint propagation

Â algorithm, okay. Right, the constraint does two things.

Â Feasibility checking, you know, is it still feasible in the set, we're given

Â the set of domains. And then pruning, given a set of domains,

Â can I knock down some value for the domains of the other variables.

Â Okay, now the key point, and this is one of the topic, one of the topics covered

Â today, is that every one of the constraints in a constraint programming

Â system, has a dedicated algorithm to do, these two tasks.

Â Okay? It's going to test feasibility, using the

Â semantics, the structural the constraints, and it's going to do pruning

Â using the same information. Okay.

Â So we, so this is the strength of constraint programming.

Â You can, can explore the structure of these constraints to prune the search

Â base as best as it can. So I'm going to use a very simple

Â example, send more money. The story here is that, you know, this is

Â a graduate student going to going to school.

Â You know, he needs more money, so his father is very, and his mother is very

Â reluctant to actually give him money. And so every time he asks for money he

Â has to find a clever way of asking. And so here he's sent, you know, his

Â parents a puzzle and that puzzle is, you know, if the parents solve the puzzle,

Â they will know how much money the graduate student wants, okay?

Â So that's the story. So, essentially the person has, you know,

Â three words, send more money, okay, all right?

Â And the amount of money has to be essentially the value of these letters

Â over there. And you have to make sure, of course,

Â that the addition here is valid, okay? So in a sense you have to assign

Â different digits to all these letters, such that addition is valid.

Â And then you will have, you know, essentially the amount that needs to be

Â sent. Okay?

Â So, now I'm going to show one model, okay, for solving this puzzle using

Â constraint programming. It's not a good model, okay, but it's,

Â it's just, you know, a model for illustrating constraint propagation.

Â So, big disclaimer in many of the, many of the examples that I'm going to use,

Â the entire, you know, class, is that there are many, many models that should

Â be better than the ones that I'm proposing.

Â They are typically chosen to illustrate different principles.

Â Okay, so this a model like we would do in kindergarten, in the sense that I'm

Â going to do, you know, column-wise, you know, digit-wise addition and use

Â carries. Okay.

Â So when you look at this thing here, okay, so you can see that you know, I'm

Â going to start with the value d and e and summing to y.

Â Okay? I'm going to get a carry c 1.

Â Okay? And that carry is basically going to, you

Â know, be used for the second, for the second column.

Â And then, I'm going to generate another carry for the subsequent one and so on.

Â Okay? So, in a sense, the decision variables

Â here are going to be of two types. They are going to be the letters, okay

Â the initial letters of the puzzle, and then they're going to be the carries,

Â okay? And the letters can take the value

Â between 0 and 9, they are digits, okay? And the carries of course will take the

Â value 0 and 1, okay? So, that's the basic principle here.

Â Okay? And so this is one of the models, okay,

Â that, that, that you could write. I told you this is not the best model

Â that you could write, but this is the model that will illustrate constraint

Â propagation nicely. Okay, so what you see at the top over

Â there, okay, so these are basically all the letters that you have, okay.

Â So so, so in this particular case you have you know, the letter s, the letter

Â e, the letter, you know, n, and so on and so forth.

Â You have them arranged for the digit between 0 and 9.

Â And then you have the two sets of these different variables.

Â Okay, so you see that this is a variable value for every one of these letters,

Â okay, which have to be digits, okay, between 0 and 9.

Â Okay, so for every one of these letters that you see at the top, you will assign

Â a particular digit. Okay?

Â And then you have the carries. There are four of them.

Â And the value of them, for the carries is 0 or 1.

Â And then what you see here are the constraints for the problems, okay?

Â So the first ones are basically telling you that all the letters have to be given

Â a different digit, okay? So this is like you know in the map

Â coloring or in the, in the Queens problem, okay?

Â Basically not equal constraint between all the variables.

Â Then you see that the value for s and for n have to be different from 0.

Â These are the most significant digits of these two numbers.

Â You want them to be different from 0. Then you have the value that the carry

Â for the last carry has to be equal to m. When you actually look at this particular

Â equation. Okay, so this is the last column.

Â 7:17

And then, and then, essentially you have all the other constraints that are

Â looking at every one of the column and putting and, and expressing the addition.

Â And it's always, in general, it's always one carry plus, you know, a couple of a

Â couple of digits, okay, for, for the letters.

Â And then on the other side you will have one other digit.

Â And you will have essentially 10 times the carry.

Â And that's what you see for every one of these constraints.

Â So you always see the ten times the carry at the end of the equation.

Â Okay? So that's essentially the model here.

Â Okay? So it's a set of not equal constraints,

Â an equation, and then a set of other equations carrying you know the,

Â basically, every one of the addition for every one of these columns.

Â Okay? So this is the search space.

Â Okay? So the search space, initially, what you

Â see there are all the digit values, okay, and you see all the letters over here.

Â You see also the carries there, and these carries can take only the values 0 and 1.

Â Okay, and once again, you know the key point here is that we are going to knock

Â down many, many, many values from this search page, and that's the goal.

Â And in this particular case, there are two things that are going to be

Â interesting. It's how much we prune, okay, using

Â these, these constraints. And it's also the constraint propagation

Â itself. We're going to do something with one

Â constraint that are going to wake up another one which is going to propagate

Â again and so on and so forth. And that's this kind of propagation which

Â is interesting. And this is what we are trying to

Â illustrate today. Okay.

Â So, this is essentially the beginning of the, of the propagation.

Â Okay. So you have the not equal constraints.

Â These not equal constraints are not doing anything initially, because the variables

Â have all the possible values. And then you have this interesting thing

Â here that you know, basically s and m cannot be 0.

Â Okay? And then that m has to be equal to a

Â carry. Okay?

Â So, there are a couple of interesting things are going to happen there.

Â Okay? So, when you see, you know, that m that s

Â cannot be 0, you're going to knock down the value 0 from s.

Â When it, you know, m is not equal to 0, you just knock down the value 0 from m.

Â And then you have this interesting constraint, which is basically saying

Â that the carry four is equal to the digit assigned to m, okay.

Â Now, the carry is 0 and 1, okay. At this point, essentially m is 1 to 9,

Â so there is only one value which is common to these things, and that's and

Â that's the value, and that's the value 1. So these two guys are going to be

Â assigned to 1, okay? And that's what you see here.

Â Immediately, the system is deducing that. Okay?

Â And usually once you do that, you know m, you know every, every digit, every

Â letter, of course has only one value, all the other values are ruled out.

Â We also know that all the digits have to be different, okay?

Â So basically these non equal constraints are going to propagate and remove the

Â value one for all the other, all the other letters.

Â Okay? And that's essentially the state of the

Â search space after this you know, a couple, you know, this not equal and this

Â equality constraint. The last equality constraint that you saw

Â there, okay? So not very interesting you know, right

Â now. This is mostly what we have seen before.

Â So things are going to get more interesting when you see this actual

Â equation over there, right? And so now, we have to find a way to

Â actually process that equation, okay? So I'm here right.

Â And this is the equation on top of me, okay?

Â So one of the things that we're first going to do is to take this equation and

Â simplify it given the current state of the search space.

Â Right? So we know that m is the value 1, so when

Â we see, you know, the value of m we can replace that by the value of 1.

Â So the equation becomes a little bit simpler, okay?

Â And now what we're going to compute is, we're going to, to make sure that this

Â constraint can be satisfied, we're going to compute the value, the, the, the

Â set of values at the left of the equations and the set of values at the

Â right of the equation. Okay?

Â And obviously, these, you know there has to be a non-empty intersection between

Â these two things. Okay?

Â So, we're going to compute the range of, of the left, and the range of the right

Â of the equation, okay. So the range of the left is 3, 11, okay.

Â And I want to go slowly and tell you how we get that, because this is kind of

Â interesting, okay. So, we have to, so this is essentially

Â how you compute it, okay. And every one of these values that you

Â see there is computed in a very systematic fashion, okay.

Â So, look, the 0, which comes here, okay, the 0 is from there, comes from the value

Â of the carry, of carry of the carry 3. So we have two possible values for carry

Â 3, 0, and 1, okay? Now if we try to bounce, you know, to

Â have the smallest possible value for this left turn, we take the smallest value for

Â carry 3 and that's 0. And that is the 0 that you see there.

Â Okay? So the value 2 there is the same thing

Â for s. Okay?

Â So we look at, what is the smallest value that s can take and that is what you see

Â over there. And then usually we get the 1 that is the

Â value of m that, you know, that is already fixed.

Â Okay? And so this is the lower bound on the

Â value of this expression in the current search space.

Â Now, we do the same thing for the upper bounds.

Â And in the upper bound, what you are trying to do is to find a maximum value

Â for that term. Okay?

Â So when we see a variable like this carry three, we take the largest value, and

Â this particle case, it's 1. Okay?

Â then we do the same thing for, the value of s.

Â which is, which is nine. Okay?

Â And that is the value that you see there. the value that you see there.

Â Okay. So that's a value of 9.

Â And then we also have the 1 which comes from the value of m.

Â Okay, and that's how you get 3 to 11, okay.

Â And we can do that, and we can do that for the others, right, which is basically

Â giving us 10 to 19. I won't go into details, I won't bore you

Â into the details, but at this point, essentially, I know what is the range of

Â the left side. I know what is the range the right side.

Â Now, to have a solution to these constraints, the intersections between

Â these left and the range of the left and the range of the right side have to be

Â non empty. And so this is what I'm computing here.

Â I'm basically looking at these two ranges, and taking the intersection.

Â And the intersection has to be, you know, 10, 10, 10 and 10 to 11, okay?

Â So now, I know that this intersection is not empty, so at this point, you know, I

Â believe that there is a solution, okay. So I also know more information.

Â I know that this term here has to range between 10 and 11.

Â If I have a solution. And same thing of course, for the other

Â term. So I'm going to use that information to

Â start pruning the search space. Okay?

Â So what I know is that, if I take the left term, okay?

Â I know that it has to range between 10 and 11, okay?

Â And now, I'm trying to say, oh, but how can I prune the search base using that,

Â okay? So let's, you know, remove all the mass.

Â And now I have just this equation there, okay?

Â And I see that, you know, 10 has to be smaller or equal to the carry 3 plus the

Â value of s plus 1. And that is to be smaller or equal to 11,

Â okay? Now, let's assume that I'm trying to

Â prune, you know, to prune the value of s. What can I do?

Â Well I can first you know, take the 1 which is in the equation and move it on

Â the right and the left-hand side. And then I have to say, oh, I have to

Â remove this carry 3, right? So I'm going to push carry 3 on the left

Â and a carry 3 on the right as well. And so now, the value of s can be bounded

Â by these two expressions that you see there, right?

Â And so what I have to do now, is once again, you know, I want to be very

Â conservative here, right? So I want to see what is the smallest

Â value that s can take, okay? And I also want to see, but what is the

Â largest value that s can take? So when I evaluate this expression, I

Â have to find a way to find the smallest possible value, because if I'm not

Â conservative, I can prune solutions that, I can prune solutions.

Â And the only thing that I want to do is prune values which appear in no

Â solutions. Okay?

Â So what I'm going to do here is to look and say, okay, the left-hand side, okay,

Â has to be made as small as possible. How do I do that?

Â Well I have a minus you know, carry 3. So I have to make this, this carry 3 as

Â large as possible, because if it's large then I subtract a lot of values, and that

Â value becomes very small. Okay?

Â So how do I make carry 3 as large as possible?

Â I take the value 1 for that, okay. And I take the value 0 to make it as

Â small as possible, such that I have the largest term on, on, on the right of the

Â equations. So essentially what I get there is that

Â the value of s has to be essentially a greater or equal to 8, and smaller or

Â equal to 10. So this interesting, right?

Â So because at this point I can prune the search base dramatically for s, right?

Â So I remove all these values up to 8 and 9, okay?

Â And this is what this equation has told you, and I have only looked at one side

Â of this equation, essentially, right? So if I look at the other side, okay?

Â I know, you know, I have to make sure that this side, now, also range between

Â 10 and 11, okay? And so, so I can do exactly the same

Â reasoning, okay? So I take these two things, I put them

Â there. And assume that I'm interested here in

Â looking I know already that the carry 4 is equal to 1.

Â So I get this expression here. Okay?

Â And then I can prove the value of, of o at this point, okay?

Â And basically, it becomes the, you know o is to be basically, between 0 and 1.

Â And I can, in one step, prune a lot of value for o as well.

Â Okay? So all these values here you know, for

Â letter o have been removed. At that point, there is only one left,

Â which is 0, so I'm going to assign it. As soon as I assign it, all the not equal

Â constraints, you know linked to that variable are going to stop because now

Â that variable is only one value. That's when this pr, you know, this,

Â this, these contraints are propagating. Remember last lecture, okay.

Â And so, in a sense, all the other values, all the other variables there are

Â going to propagate there, using these not equal constraints, okay.

Â So, that's what you see there. Okay, so we go back to these constraints

Â there, propagate them, and now the search space has been reduced.

Â And the only variable, the only digit, the only letters that can take the value

Â 0 is o, okay. So that's, so what we have done so far is

Â propagating all the constraints up to the one which is highlighted there.

Â Okay, so we propagated the non-equality, the very simple equality, the first

Â equation, and we are looking at the second one now, okay.

Â Second one is exactly the same reasoning. As I have shown you.

Â We are looking at these equations like that, and we are going to do the bound

Â reasoning that I've shown you. Right?

Â We simplify it a little bit using the value of the variable.

Â We know that this guy is between 2 and 10.

Â Okay? If this guy is between 2 and 10, we know

Â that this guy, to satisfy the constraints, has to be between 2 and 10.

Â And that's what we are looking at. Okay?

Â So now we know the value of n. Okay, plus 10 times the carry 3 has to be

Â between 2 and 10. Okay?

Â So let's assume that we are interested in carry 3.

Â If we are interested in carry 3, we have to take this value of n and move it on

Â the left and the right, okay. So that's what we do, okay?

Â And this is what we get. We get 10 time carry 3 there, okay?

Â And then you have the value On the left and the value on the right for the lower

Â and upper bound, okay? Now you look at this 10 times carry 3, so

Â once again we have to make this guy as small as possible and this guy as large

Â as possible to be conservative right? Okay, so to make this guy as small as

Â possible, what do we do? We take the largest value for n, what is

Â the largest value for n? It's 9, okay?

Â So and, the other side, the upper bound, we have to make it as large as possible.

Â And so, since this value's negated, we have to make it as small as possible so

Â we will take the value 2. Okay?

Â So at this point, we simplified the equation, okay, which becomes, you know,

Â -7 is smaller equal to 10 times carry 3, smaller or equal to 8.

Â The left side is boring, okay, so the right side is more interesting, because

Â its fourth is carry 3 to be equal to what?

Â To be equal to 0. Okay?

Â So, this guy is not going to be 1, it's going to be 0.

Â And now, something really interesting happens.

Â Right? So, what we did, what we just did now, is

Â looking at this second ineq, the second equations, and we found a new value here

Â for carry 3. Now, the interesting point here is that

Â carry 3 is also happening in the first equation.

Â So, now, we are basically saying oh, but that equation has some more information.

Â So I will go back and propagate that information.

Â Okay. So remember the fixed point algorithm is

Â always looking at this loop, and always taking, you know, looking at the

Â constraints and until you cannot propagate at anything, it's going to look

Â at constraints and trying to actually propagate them again.

Â Now when a value of variable like, oof, I show you here, okay, has changed, it's a

Â good indication that you should actually reconsider that constraint.

Â So the constrain propagation algorithm is going to take that constraint and try to

Â propagate it again and try to obviously to find if its still feasible and so on.

Â Okay? So we're going to go back to that

Â constraint. So this is the constraint that you see

Â there. [NOISE] Okay?

Â And we're going to simplify it, because we have a lot more information at this

Â point, right? So you see the, the value of carry 4, we

Â know, we know the value of o, we know the value of n.

Â And so, this constraint becomes really simple at this point.

Â It becomes essentially the value of s is equal to 9, okay?

Â So once again, what we can do is prune the search page, okay?

Â And the remove the value 8 from the value of s, assign the value 9.

Â Of course you are going to propagate all the non-equal constraints and remove all

Â these values. And this is all the search space has

Â removed, okay, has been pruned at this point, okay.

Â So essentially what I have shown you here is all these constraints are basically

Â you know, influencing every other ones. Okay?

Â So, constraints are going to propagate. Okay?

Â Use it's dedicated algorithm to remove value from the variables.

Â Now, some of these variables appear in other constraints.

Â These other constraints are going to be propagated again.

Â Remove more values, which are going to propagate other constraints, and so on.

Â And this fixed point algorithm is really what is the core of constraint

Â programming. So you basically propagate all these

Â constraints until you cannot deduce anything.

Â And also, you have a dedicated algorithm for every one of these constraints.

Â Okay? So, let me go into the, the, the, the, a

Â little bit of the mathematical details to actually implement this.

Â Which are reasonably simple here. Okay?

Â So, this is essentially a cons, this is a linear inequality that I'm going to show

Â you how to propagate optimally. Okay?

Â So, you see that the left-hand, the left-hand side here is basically a sum of

Â product. Okay?

Â A, i, you know, x i. X i, a decision variable, a i is

Â basically constant. So that's the left-hand side, the

Â right-hand side is similar. The y's are basically decision variables,

Â the b's are constant, okay? So what I'm interested in, what I'm

Â interested in here is essentially propagating that constraint optimally.

Â Removing as many values as I can, from the domain of the variables.

Â So I'm going to assume that the domain of x i and, and y i are denoted with the

Â convention that I used last time. So d x i is the domain of x i.

Â And d y i, y j is the domain of y j. And now what I have to do is propagate

Â using that information these constraints, okay?

Â So the first thing that I have to do is to test if it's feasible, okay?

Â And the feasibility test here is going to be very, very simple, right?

Â So how do I make sure that I can, how do I test, you know, if this constraint is

Â feasible given these domains for these variables.

Â Well, what I want to do is essentially take the left-hand side and make it as

Â large, as large as possible, right? And take the right-hand side, and making

Â it small, as small as possible. And if, if by, if the smallest values and

Â the largest values don't satisfy the constraints, I know that nothing will

Â satisfy the constraints, okay? So, the feasibility test.

Â Look at the left-hand side and replace every decision variable by the maximum

Â value I can take. If look at the right-hand side and look

Â at every decision variables, and take the smallest value that it can take.

Â So that's the min in this domain and then I test.

Â Now I have no decision variable left, only constant.

Â And I'm basically test if this is, this, this inequality is satisfied or not.

Â Okay? If it's satisfied, feasible, if it's not,

Â it's infeasible. Right?

Â So, now essentially, I, let's assume that it satisfies all.

Â Okay? Otherwise, I can't prune.

Â Right? I already pruned the note in a sense.

Â And so what I'm going to assume here for pruning, is that I have two values left,

Â l and r, for left and right. Okay?

Â Which are basically, the l is basically denoting the largest value that the

Â left-hand side can take. And r is denoting the smallest value that

Â r can take. Okay?

Â So I'm going to use that for the pruning algorithm.

Â You remember, l is the largest value for the, for the left-hand side.

Â r is the smallest value for the right-hand side.

Â Okay? So then this is how I prune the search

Â space. Okay?

Â So I want to look at x i. Okay?

Â So let's, let's look at x x i. Okay?

Â So what I know is that a i x i has to be greater than what?

Â So, look at this, look at the, the, the initial constraints over there.

Â I'm going to look at the right, I'm going to look at the right-hand side.

Â So the right-hand side is r, okay, so that's going to always be there.

Â And then, what I have to do is take all the other variables here, okay, and move

Â it on the other side, so this, they have the largest value there.

Â And those values are essentially l, except that, I don't want to double count

Â x i, right? So I have to, I have already counted

Â inside, I have already counted inside l, so I have to remove it.

Â I have to remove a i times the domain of times the largest value in the domain of

Â x of, of the, of x i. And that's what I'm doing in this

Â expression here, right? And so now, I know that, I know that this

Â is valid. Okay?

Â So, I know that a i xi has to be greater than that for the constraint to be

Â satisfied. And that leaves me this pruning rule that

Â you have here. Okay?

Â So, I basically take this expression divided by by a i.

Â And since I want to be conservative, I have to run, well, well, that, that,

Â that's fine. So, since I'm working with integers I

Â have to run up of course, if it's a fractional values.

Â Okay? And this is what you see here.

Â Okay? So, this is what you see here, sorry.

Â so what you see there, is that I'm basically taking the seal of that

Â expression over here. Okay?

Â And this is how I prune. And of course, y, for y I"m going to do

Â exactly the same thing, except that I"m going to do, I'm, I'm going to, I'm

Â going to subtract the value of y j. And then I'm going to divide by, you

Â know, b j. And then I'll, instead of taking the the,

Â the ceil, I'm going to take the floor. And I'm going to basically update the

Â upper bound of y j. So in a sense, so what I do is that I

Â update, the lower bound of the axis, I update the higher bound, the upper bound

Â of the y's, using these two very simple rules that can be computed efficiently,

Â which essentially, you know, as I told you, use the largest value for the x i,

Â in the domain of the x i, and the smallest value in the domain of the y i.

Â Okay? So lessons from this lecture.

Â First that, you know, you have a dedicated algorithm for every one of the

Â constraints. The constraint propagation algorithm is

Â really rich, it's going to propagate these constraints until you cannot get

Â information. And so as soon as you accumulate raw

Â information in one variable, it's going to propagate to another one, it can come

Â back and propagate all these contracts, okay.

Â And this, and in this particular case, the bound propagation algorithm is very

Â easy to compute. It's basically reason about, you know,

Â the, the, the upper bounds and the lower bounds on every one of the variables.

Â Okay? So we're going to see in the next couple

Â of lectures, you know, different modeling techniques for constraint programming,

Â and also different techniques for actually pruning the search base.

Â Okay? See you next time.

Â