0:00

Okay guys. You know, I talked about the language of

Â constraint programming the last time and that I was presenting an overview of what

Â it is. You know, I lied.

Â Okay. So there is one more thing that I need

Â about, that I need to talk to you about and this is global constraints.

Â Okay? So global constraints are one really

Â important feature of the language of constraint programming.

Â They are part of this richness and the ability to express complex substructure,

Â okay. They are a critical path of any

Â constraint programming system and this is a very active, you know, research area in

Â the field, okay. So, what is the global constraints?

Â The global constraints capture the, the, the combinatorial substructure arising in

Â many applications. So, the good analogy here.

Â Is essentially Lego blocks. Okay?

Â So you, when, when you buy Legos, you have a big set of pieces that are

Â encapsulate things that you want to build from.

Â Global constraints are exactly like that. They are capturing substructure that are,

Â that are arising in a variety of application.

Â And we can use them directly. We don't have to express them in terms of

Â smaller blocks. Okay?

Â They make modeling, you know, easier, they are more natural.

Â They make the model easier to read, they make the model more concise.

Â But, the real, real interesting aspect of them is also the fact that these

Â combinatorial substructure are really given to the solver.

Â We capture this structure and we give them, you know, directly to the solver.

Â And then the solver has a lot of information to do interesting things.

Â And in particular, it gives the solver the ability to use dedicated algorithm

Â for each one of these substructure. So I'm going to give you examples.

Â First, you know, I'm going to show you the modeling and then I'm going to tell

Â you how these things can actually help you from a computational standpoint.

Â So, what you see here is probably the most famous, you know, global

Â constraints, the alldifferent constraints.

Â And these constraints is basically saying that the variable x1 to xn have to be

Â given a value, have to be given all different values.

Â So no two variables in x1 and xn can, can take the same value.

Â Okay? Now remember, you know, we had this

Â beautiful queens example in the previous lectures?

Â Okay? And what that was basically saying is

Â that all these queens, okay, have to be placed on the chessboard.

Â Such that they were not on the same row, the same upward diagonal and the same

Â downward diagonal. Okay?

Â Well, you can essentially express the same example with three constraints and

Â that's what you see there, okay. Same decision variable but now instead of

Â saying all these rows, you know, in which the, you know, the queens were placed,

Â had to be, you know, pairwise different. You just specify one constraint which

Â says all the rows have to be different. Okay.

Â That's what you said. That's what you are stating there.

Â Now, if you look at the other constraints, these guys, okay.

Â So what you see once again is that, you know, you see row i plus i, row j plus j.

Â Essentially what it is that you have a bunch of expression row i plus i row j

Â plus j row k plus k and essentially all these things have to be different and

Â that's what you express in this constraint.

Â Okay? And so that's once again a-alldifferent

Â constraints. Okay?

Â And these all different constraints is going to capture the upper diagonal and

Â you'll have the last alldifferent constraint which is going to capture the

Â lower bound. Now you see that this operator all over

Â there, essentially this is [INAUDIBLE] comprehension, okay.

Â So essentially what it says is take all i in r, okay?

Â Take the, the collection of expressions that you see over there, which is in this

Â particular case, you know, row i plus i, and collect all these in an array, and

Â then that's, that's the array that you have as a result, okay?

Â In this particular case, this array's going to be passed to the alldifferent

Â constraints, okay? So, essentially, this is collecting a

Â bunch of things, and then saying that all these variables, or expression, in this

Â particular case, have to be different. Okay, so in a sense we can express this

Â screen problem with three constraints. Okay?

Â Now why would we ever do that? It seems more complicated and so on but

Â what I'm going to show you is that this has a lot of computational advantages.

Â Okay, so let's look. You know, you know from now on from, you

Â know, previous lecture that every constraints has two goals in life.

Â The first goal is to, is to do feasibility testing.

Â You want to know if the constraints is feasible.

Â Okay? Remember we had a constraints.

Â We have essentially for every one of the variables the domain.

Â Okay, so that's a set of values that a variable can take.

Â Okay? So, we often use this notation here, you

Â know, this is a constraint and then we said that d1 is the domain of x, of x1

Â and then d2 is the domain of x2 and so on.

Â Okay? So, what is feasibility?

Â Feasibility is finding a value in this domain such that when the variables are

Â assigned it's variables the constraint is satisfied and that's essentially what

Â this formula is basically telling you. Does there exist a value in the domain of

Â x1? Okay?

Â Such that, and there, there, such that if I, so that I can find another value for

Â the you know, v2 in the domain of x2, and v3 in the domain of x3.

Â Such that, when I assign all these values to the cons, to the variable of the

Â constraint, the constraint is true. That's feasibility testing.

Â Okay? Now, let's look at this constraint here,

Â okay? So, we have the alldifferent, okay, which

Â is on three variables, x1, x2, x3. You know, cannot be much simpler than

Â that, okay? And then, for every one of these

Â variable, okay, so, we have a domain. And in this particular case, three

Â variables with a very simple domain, value 1 and value 2.

Â Okay? Now, so in a sense, all different and

Â then these other domains. Okay?

Â Is this feasible? Okay.

Â No, it's not. Okay.

Â Why is not feasible.Okay. It's not feasible because we have three

Â variables and we have two values. Okay?

Â So people in computer science code, that the pigeon hole principle, I have never

Â seen a pigeon in a hole but anyway. So this is the pigeon hole principle.

Â Probably pigeons are looking for holes and if you have three pigeons and two

Â holes, they can't all fit in the hole. Okay, in the holes.

Â Okay, so is, in a sense here what it's telling you, three variables two value,

Â impossible. You can't have feasibility.

Â Right? So we know that the global constraints is

Â going to say no, no, no, this is not feasible.

Â Okay. Now, if we look at, you know, the first

Â formulation that we had when we were using the queen's example we had

Â essentially three constraints to express the same thing.

Â Right? So we said x1 can not be equal to x2.

Â X2 cannot be equal to x3 and that x3 cannot be equal to x1.

Â Now if you look at every one of these constraints independently.

Â Okay. Do the same test that we just did for the

Â that alldifferent. What do you get?

Â Well. For the first constraint I can take the

Â value 1 for x1 and the value 2 for X2 and this constraint is fine.

Â It's satisfied. Okay.

Â You look at the second constraint and you can do exactly the same trick.

Â Of course this time is the value x2 and the value x3.

Â Okay? But essentially it's true as well.

Â And the third constraint is true as well. So all these constraints, when you look

Â at them independently, they are fine. Okay?

Â So, the system is going to say, yeah, you know, the set of constraints look

Â satisfiable. Okay?

Â Although we know for sure that they are not.

Â Okay? So, that's one of the big impact of

Â global constraints. Okay?

Â They can actually detect infeasibility earlier in the search space.

Â Therefore, they make your search space smaller, and your search more efficient.

Â Okay? So, in a sense if you think about it,

Â this is the computation model of constraint programming.

Â Right? So, you have this domain store, it has

Â the domain of the variables. And gravitating around if you have all

Â the constraints. These constraints only talk to the domain

Â store. They don't talk about each other.

Â And because of that, if you handle them independently, they don't necessarily

Â communicate. Right?

Â So, they can talk to the same domain, and that's what you see.

Â Right? So this is the first constraint, talking

Â to this two domain. The second constraints have a domain in

Â common, and another one. The two constraints have again another

Â domain in common and another one. And so you see that they are all linked.

Â The path can be long, but they are all linked.

Â But when you reason about them independently, you lose that length.

Â Okay? What the global constraints is saying,

Â okay, so let's encapsulate all these constraints inside one global

Â constraints, which talks to all the these domains at the same time and now I can

Â actually detect infeasibility. Okay?

Â So, so now we have done only the first thing that a constraint does for a

Â living. Right?

Â Which is testing feasibility. The other thing a constraint does for

Â living is pruning. We want to look at these domains and see

Â if we can knock down some of these values, okay?

Â Because that reduces search space, also make the search more effiecient.

Â Okay, so the question that we have is given a variable a value vi inside the

Â domain of variable x i. Okay, can I use sin, the value of vi to

Â xi and still find the solution to that constraint.

Â Okay? So in a sense what that means is that I'm

Â assigning vi to xi but I want to find out if that value seems dominant of the other

Â variables such that the overall constraints is going to be

Â satisfied.Okay? So how do I do that?

Â This is the formula right? So I'm assigning xi to the i, okay?

Â And then I want to find a value v1 for v1.

Â Value v, i minus 1. Inside, you know?

Â For, for the variable xi minus one. And so on and so forth, such that this

Â constraint is true, okay? So I pick up one variable, one value.

Â And then I see if I can verify find values in the other domain of the

Â variable. In the domain of the other variable such

Â that the constraint is satisfied, okay? So look at this, okay?

Â So this is once again alldifferent constraints.

Â Now I have three domains, one two for variable x1, one two for variable x2, and

Â then one through three for variable x3, okay?

Â And I'm asking you, can I actually prune the search space, okay?

Â 9:03

And the answer is, yes I can, okay? Why?

Â Well, we know because of this beautiful pigeonhole principle, that if I look only

Â at x1 and x2, I have two variables, and they can only take two value, 1 and 2,

Â okay? Therefore, if x3, the friendly x3,

Â actually take either 1 or 2. No, we won't find a solution, okay.

Â So what you have to, what you can deduce easily, is that x3 cannot be 1 and cannot

Â be 2 it has therefore to be 3, okay. And therefore, you reuse the search

Â space, you know. X1 and x2 can take either 1 or 2,

Â provided they have a different values, okay.

Â So the only pruning that you can get is remove the, removing the value from 1 and

Â 2. Okay?

Â Now, that's the pruning that we can get. But once again, if you don't express the

Â global constraint, if you use the composition here in terms of pair wise

Â constraints, you would not prune anything.

Â Okay? Because essentially, for x3, you know,

Â when you look at x3. X3 and x1, well they can, you know, x, x3

Â can take the value 1 and x2 and x1 can take the value 2 and that's fine.

Â X3 can take the value 1 and x2 can take the value 2 and that's fine as well.

Â So you never detect that you actually have to remove the value one and two from

Â x3. So the second big benefits of global

Â constraints. Not only do they detect feasibility

Â sooner, but they also actually, make it possible to prune the search space more.

Â They remove value from the domain of the variable.

Â And why is that important? Because now the domain are smaller

Â another constraint can come in and do more reasoning and maybe find an

Â inconsistency or maybe prune new values from the domain which will in, in turn

Â probably find some inconsistency or some more values from the domain, okay.

Â So, this fixed point is very important. That's why you remove the search space as

Â much you can. Okay?

Â So the million dollar question though is what?

Â Can I actually, you know, detect feasibility and achieve this optimal

Â pruning for this global constraint? Okay.

Â And the answer to that sometimes we can, sometimes we cannot.

Â Okay. So sometimes we will able, we will be

Â able to detect feasibility and I will show you examples of that.

Â And sometimes you will have to relax your standards.

Â Okay, which basically means that you won't be able to prune everything or you

Â won't be able to detect insatisfiability all the time.

Â but, but you will still get some pruning and detect visibility early, okay.

Â the other thing that you can say is I'm going to sacrifice computation time and

Â essentially some of these algorithms and one of my students became an expert in

Â finding exponential algorithm from pruning constraints, okay?

Â And what, what you do there is you sacrifice time but you will have the

Â optimal pruning. You will detect infeasibility as soon as

Â you can, okay? So the answer here is sometimes some

Â global constraints you will be able to deal with very efficiently, sometimes you

Â will have to relax your standards. Okay, now I told you when, you know, in

Â the advertisement of this class that, you know, you will never have to solve a

Â sudoku in your life, okay? And I'm going to keep that promise, okay?

Â And so this is a sudoku and we want to solve it using constraint programming.

Â Okay? So this is a very simple model on how to

Â do that. Okay?

Â So the decision variables are very easy right?

Â So you look at everyone of these square, little square everywhere.

Â You know, there will be a decision variable associated with that and that

Â decision variable will be the number which is associated to that square.

Â Okay? The digit.

Â Okay? So essentially that's what you see there.

Â You know these are the decision variables over there.

Â Okay, they are basically [UNKNOWN] a matrix of, of, of variables, and these

Â variables take the value between one and nine.

Â Okay? Now, the constraints of these problems,

Â you will have different types of constraints.

Â The first set of constraints will be the fixed position.

Â Okay. So when you look at this thing, there are

Â a bunch of fixed positions all over the place.

Â We'll have to fix these values, these variables to these values.

Â And then once again, we have only three types of constraints, okay.

Â Well, actually one type of constraint but three different ways of stating that,

Â okay. So we have only alldifferent constraints,

Â but some of them are going to be on the rows, some of them are going to be down

Â the column and some of them are going to be on the squares, okay.

Â So when you look at the first one. Essentially that constraint, is basically

Â stating, that all the values on a particular row have to be different.

Â The second one is basically saying that all of the values in a column have to be

Â different. And the third one is basically, you know,

Â you look at the square, you know, three by three there, and you are expressing

Â that all these values have to be different.

Â These are the constraints of the Sudoku and that's all you have to do.

Â So this simple program. Is why is at least part of the reason why

Â I would never do a sudoku in my life, right?

Â You know it's so simple, right? So the next thing that I want to show you

Â is actually this is a very efficient way of actually solving this thing.

Â Okay, so look at this puzzle. Okay so the first time I run the program,

Â I traced it on this particular example. It deduced that, of course it, it fixed

Â all these position, and then it deduced that this value has to be 2, okay?

Â Now, that's very interesting, okay? So, I was like how did it do that?

Â Okay? And so you have to look at a couple of

Â things, okay? So, you see, you know, there is there is

Â a 2 over there. Right?

Â So, which basically means that I cannot put a 2 over here, okay?

Â There is no way I can do that. Okay, and then you have a two over here,

Â which basically means it can't have any two on this last line, okay?

Â So the tree position where I can actually put a two is here and these two gaps,

Â right? Okay?

Â So but look at, look at the, the square here in the middle.

Â Once again, I know that I have a two and therefore, I cannot put a value over

Â there, okay? Now I also know, what do I know?

Â Okay. So I know that I have a 2 over here.

Â So these guys here, cannot get a value of 2.

Â So the only two positions where I can get a 2 here, is these two guys.

Â Okay. These 2 guys can take a two.

Â I don't know which one, right? Okay?

Â But at least one of them has to take a 2. Therefore what I know is this guy, cannot

Â have a 2 over here. Okay?

Â And therefore, the last position at which it's get a, get a 2 is over there.

Â That's what the system did. That's what this pruning for the all

Â different constraints were able to do. It's magical, right?

Â Okay, so if you do that, then it's going to know, going to continue deriving

Â all these values all over the place. That's what it gets, just propagating

Â these constraints, okay? And then, the system will make a choice.

Â It will assign the value 5 at the top over there.

Â Choop! Here.

Â And that it will make more deduction than when you assign one more value over here,

Â okay? So there's a value of 4.

Â And then propagate and find a solution, and that's it.

Â Two choice, no back-track, solution immediately.

Â Okay. Now you have to know that sudokus are

Â easy for us, and the reason is that they have to be easy for human, which

Â basically means that human don't like to make choices, so these sudoku are

Â actually designed so that you can mostly deduce the solution and don't go into

Â exploring a huge tree. That's why these things are really easy

Â for constraint programming in general. Okay, so, so we have seen now essentially

Â global constraints and global constraints are these very important area of

Â constraint programming. There are a lot of people actually

Â exploring this. Okay?

Â And, I want, I want to show you one more type of constraint which is the table

Â constraint. And it's probably the simplest global

Â constraint, okay? And so this is an example for you to

Â understand. I have three variables okay?

Â x, y, and z, okay? This is the domain of the variable 1, 2

Â 1, 2, and then 3 ,4 ,5 for, for z. Okay?

Â And then essentially one of the things we can think of is, you know, what are the

Â possible combination of all these variables, okay?

Â What are the total possibilities? And essentially there are 12 of them,

Â okay? So you could see each product between,

Â you know, the domain of x, the domain of y, and the domain of z, okay?

Â So that's what we have, okay? So in this particular case there are 12

Â possibilities. So what a table constraints is doing, is

Â actually specify a subset of these possibilities as the legal, you know,

Â assignment of these variables. So, in this particular case, we have four

Â of them, okay. So you see that the first one is 1, 1, 5.

Â X is equal to 1, Y is equal to 1, and Z is equal to 5.

Â The second one is 1, 2, 4. That's what you see here, okay.

Â And so in this particular case, the legal combination is 1 for x, 2 for y, and 4

Â for z. Okay.

Â And so once again what is interesting to see is what happens when you get more

Â information. Okay.

Â So assume that I have more information about z.

Â What's going to happen? Well, I know that z cannot be equal to 5.

Â What does that mean? Okay, so the value z there is not legal

Â anymore. I have to remove that combination.

Â I have to remove all the combinations where I have actually z is equal to 5.

Â There is only one here, okay? And now, essentially, I look at the, I

Â look at the other variables, and what do I see?

Â Look at this guy, look at y. The only value which is left in the

Â column of y is 2. So I can immediately deduce that, in a

Â sense, y has to be 2 and the value, you know, and this is what this reflect here,

Â okay? So, so, in a sense, y has to be different

Â from y, it can only be 2, okay? So that's essentially the table

Â constraints. Once again, it's a very useful

Â constraint. It always specify a subset of a cartesian

Â product. For all the variables.

Â Okay? So let me conclude this lecture by one

Â more thing, okay? which is how can we find optimal solution

Â in using a constraint programming? So remember we discuss graph coloring or

Â map coloring actually In the first two lectures, okay?

Â And so what, what I'm doing here is generalizing a little bit of that

Â example, okay? And instead of using colors, I'm using a

Â number from 1 to 4, and what I'm going to do now is not only color this country

Â such that they get a different color, in particular, in this particular case a

Â number between 1 and 4. But I also want to minimize the number of

Â colors that I'm using. Okay?

Â So basically here, I'm basically saying, okay, minimize, okay, what the maximum

Â color that this variables can subject to the fact that two adjacent countries have

Â to be colored differently, okay? So, I can do that.

Â Okay, so that's a model which is essentially optimizing the number of

Â colors that I have to use. In all the possit-.

Â Selecting essentially the solution, the feasible solution, which uses the, the

Â fewest colors, okay? How do I do that?

Â In constraint programming, as I told you, the focus is on feasibility.

Â And what you do when you're trying to optimize is you're trying to reduce

Â optimization problem to feasibility. You essentially solve a sequence of

Â feasibility problems. You find a solution and then you put an

Â additional constraint which says, oh, but the next solution is to be better than

Â the one that I just found. Okay so when we find a solution with four

Â color we are going to say I want to find a solution which you're only using three

Â colors. Okay, so we are guaranteed to find an

Â optimal solution. You know, theoretically.

Â You know, in practice it may take too long, okay and this is going to be a

Â strong method when essentially the constraints are too hard, that you add as

Â essentially a strong pruning, okay, and this happens in a variety of problems in

Â results, allocation and scheduling, and we'll come to these problems at some

Â point in this class. Okay.

Â Thank you. That's it for today.

Â