0:00

Okay, this back, back to discrete optimization constrain programming part

one. Okay so what we are going to see today

is, we are going to introduce one more trick in our bags.

Okay, so I told you, you know optimization is a bag of tricks.

Okay. We don't call them tricks we call them

methodologies or, you know paradigms, or computational paradigms or something.

So this is one of the main paradigms to actually tackle optimization problems.

Okay? So what I'm going to do today is

basically giving you a very highlighted introduction to constraint programming.

Okay? So the basic principles.

Okay, very simple stuff, okay? And in subsequent lectures, I'm going to

go into more and more detail, and more complicated things.

But, the, the key today is intuition and what is really the essence of constraint

programming, okay? And so this is, in two words, you know,

in one slide, what, what we going to see, okay?

So, constraint programming is two things, which are interesting.

First, it's a computational paradigm, okay?

Which is very different from dynamic programming, and branch and bond that we

have seen so far. So, the key idea is, what you want to do

is look at the problem constraints, okay? And try to use them to reduce the search

space, okay? So remember, when we saw branch and bond,

we had this bonding technique, optimistic evaluation.

And the goal there was to prune the search space by using the objective

function. Here, we are going to prune the search

space by looking at the constraints. And the constraints are going to tell

you, ooh, that value. If this sort of value's taking that

value, you know, that volume cannot take that volume.

Okay? So that's what's going to happen.

We going to look at values which cannot appear in any you know, solution any

feasible configuration and we are going to remove them okay.

And therefore we going to reuse the search base okay.

Completely octagonal to the bonding techniques and these things work together

nicely okay. Now, there is a another thing which is

very nice about constraint programming. And that's why we are starting with this

one. It's that we can model problems at a very

high level. Okay?

So, essentially the, the key to designing good constraint programming is to try to

tell the server, have as much of the problem as possible.

Reveal the structure. Okay?

Tell, you know, don't try to go, you know, use irrelevant coding.

Give the structure to the server, then the server can actually explore it.

So you'll see what that means, but essentially what you want to do.

Is express, you know, large problems in terms of sub-structure, things that

building blocks. It's like playing Lego.

Okay. So you have basically they are assembling

these Lego together. Okay, and the reason is that you want to

give the solver as much information as possible.

Okay, so I'm going to start with a very simple problem, which is the eight queens

problem. So what you want to do is to place eight

queens on a chessboard, okay? Now, the first time, you know when I

tried to introduce you know, that problem to my dad to explain you know, what I was

doing he told me, but I don't have eight queens.

I told him just pretend that you have eight queens.

But I don't have eight queens. Now look, I have eight queens now.

Ooh, look, I have all of them. Daddy you can actually play the game.

Okay? So we have eight queens, that's so

beautiful of 3D printing, okay? Disclaimer, I have no you know, shares in

3D printing companies. But this is, this is kind of nice.

Okay? Anyways, so this is what we are trying to

do. Okay?

So placing these eight queens on a chessboard says that no two queens are

actually attacking each other. Which basically means they cannot be in

the same row, they cannot be on the same column, and they cannot be on the same

diagonal, upper and lower diagonal. Okay, so that's what we are trying to do.

So this is the chess board. Okay, there, and we are trying to place

these queens. Okay, so let's look at what we're going

to do. So this is the first queen.

Okay, we place it there. Now the goal of constraint programming is

to reduce the search base. We want to be sure that we remove values

that are impossible. In this particular case, these values are

impossible. No, we can't place any queens there.

Why? Because they are on the same column.

You can't place anything on the same row. That's what you see.

And then we cannot place anything on the same diagonal.

That's what you see there. OK?

So we place a second queen. There's a second queen that you see

there. OK, so once again we do the same thing.

We remove the values which are infeasible.

You know, look, this search place is getting smaller and smaller, okay, so we

place the third queen, and now nice things are going to happen, okay.

So you remove all your same row same color, and what you see at that point,

okay, is something which is kind of interesting, right?

So what do you see, is that there is one queen here, one particular column which

has only one value left. So you know that, you know, you have to

place that queen over there. So you can place it, okay?

So you place that queen there, because this is the only value that can be placed

on that particular column, okay? And then you remove values.

And then now, what you can see, is that, okay, so here you have to place a queen

again, because this is the only queen that can place on this column, and you

know that there has to be a queen on every column, because you know, you have

eight queens and they cannot be on the same column, okay?

and so, essentially, you place the queen over there, okay?

And once again, you prune the search space.

You see that again, you have to place that particular queen over there.

You place it. Okay?

Now you propagate the constraints again, and you see that oh, but at this point,

these are the two cells that are left and I have two queens to place.

So, I know that, you know, given the first position of my three, first three

queens, I can't place, you know, queens on these two stairs because they are

going to attack each other. So at this point, if I place the first

three queens over there, I know there are no feasible solution.

Okay, so what I have done here, okay, is, is, is beautiful, right.

So I if I place these three queens, just like propagating the constraints by

reducing the search space, I can detect that there are no solutions with these

three queens, okay. So I made, three positioned the way they

are. So placing three queens here is

basically, automatically, by propagating this constraint, this covering that there

are no feasible solutions. I don't have to branch on the fourth, on

the fifth, on the sixth, on the seventh, on the eighth you know, and the last

queen, okay. So what am I going to do?

I can say I can place this queen over there.

I'm going to reconsider a new position. Let's say this one And I'm going to

restart the process, propagating the constraints again.

Okay, and trying to see if I can find a solution.

Okay, so you have seen the essence of constraint programming at this point.

And the essence of constraint programming is essentially using the constraint to

reduce the search base. And the search base here is essentially

the set of values that the variables can take.

So what we have done is basically looking at which values can be removed without

removing any feasible solution. We will, we were always conservative,

only removing the things that we know cannot be placed there.

And when you do there, that, essentially you reduce the search space as much as

you can. And then, once you are stuck, you will

make a choice, okay. And that choice is going to start another

set of propagation. And another set of deductions.

Okay? And that's the computational paradigm.

Now, there are many choices. Okay?

So, what is the choice, you know, it's going to depend on the various problems.

But, you know, at the beginning, we simply are going to assume that the

choices that we deal with are basically assigning a value to a particular

variable. Now, there are many choices, and one of

the things that you know is that in optimization many of them will be wrong.

Okay, so if you have a choice and if its wrong we'll then do exactly what we've

done in branch [INAUDIBLE]. We're going to go back to a previous

choice and you know, you know reconsider it and lets say assign a new variety to a

particular variable. Okay, so that's the two assets here that

we have, okay. So we essentially constraint propagation

for removing infeasible values. The from the domain of the variable, the

set of values that a variable can take, and then we have the ability to make

choices when we are stuck, when we can't deduce anything else, okay?

So let me illustrate this. So what I want to do now, so you have the

essence. So, this is, this is essentially what

capture, what constraint programming can do.

So what I want to do now is use an even simpler example, okay?

And then look at the model and how essentially you can actually use the

constraint for pruning in such spaces. So what we're going to look is, you know

coloring a, a, a map. And so the key idea is that you have a

set of territories here. They can be state, countries, whatever.

Okay? And you will want to color them such that

two adjacent territories are not colored with the same color.

They don't receive the same color. Okay.

Now there is a beautiful theorem. Actually this is the first theorem that

was proven with the help of a computer. That every map can be colored with four

colors. So we never need more than four colors.

Okay so and essentially what we have to do is write a program which given a map

okay. And you know list of you know adjacent

territories. Is going to color the map such that no

two adjacent territories are going to receive the same color.

So this is so this is essentially what we're going to do.

And so once again, you know, what we do is we have to find what the decision

variables are. Any, with any kind of methodologies, you

know, that we will explore, like local search, like constraint programming, like

mixing teacher program. The first step is always going to be

choosing, choosing the decision variables, okay, and then expressing the

constraints in some sort of decision variables.

What are going to be the decision variables here?

Well, for every one of these territories, you will have a decision variable, and

that decision variable is going to tell you what is the color of that particular

territory, or country, if you're modeling a map of countries, right?

And then, the domain of these decision variables are all going to be all the

colors, okay? So since we are in the map, okay, we know

that we need only four colors. So we'll choose them, you know, blue,

red, green, and brown, right? Whatever.

OK. So four different colors, that's what,

that's all we need. And now the constraints are going to

basically specify that two adjacent territories can all have the same color.

Okay, and the best way to do this is to use a non-equality restraint.

Okay, so this is a model. Okay, so this is a model in a higher

level modeling language and I'm going to go over here some of these aspects.

So what you have there, is that you have an enumerated title that tells you what

other countries that we are interested in.

Okay, so this is a tiny subset of you know the European countries.

Okay. And in this particular case we're

going to use also a list of colors that's basically the values that the variables

are going to take. And we take black, yellow, red and blue.

Okay, that's what you see over there. And the next line is basically telling

you what the decision variables are. Okay.

So what you see here is that you have a set of colors.

For every country there will be one color okay, decision variable.

Which is associated with every country, okay?

And thus, essentially the color that that country's going to receive.

And this is a variable which is ranging over a set of colors.

Okay? So the, the this, the values that every

countries can take is basically black, yellow, red and blue.

Now, what you, what you are trying to do is solve, okay, this is a feasibility

problem. Okay?

We are trying to solve. You know, and find a solution which

essentially uses these four colors and satisfy all these adjacent c constraints.

Okay? So, you know that Belgium is adjacent to

France, so we want to be sure that the color of Belgium is going to be different

from the color of France. Okay?

So, you these not equal constraints saying okay, the value of these two

variables have to be different. Same thing you know between you know,

Belgium and Germany up to the very last which is basically between Germany and

Luxembourg. These two countries are adjacent so you

don't want them to be colored with the same value.

Okay so that's essentially a high level model of a constraint problem okay, and

you have these constraints that are basically specifying the relationship

between these decision variables. Okay?

So this is essentially the, the, the, the small part of Europe where you see all

the countries. Okay?

And at the beginning what the constraint program is going to do is trying to prune

the search space. But at the beginning you can't prune

anything in a sense because all the countries can take all the values.

Okay? And so nothing is going to happen at the

beginning. So these are all the possible values that

these guys can take. All the possible colors.

And then at some point you're going to make a decision because you can't

propagate anything, you cannot reuse a search space.

And you color, you are going to color, you know, beige and black.

Okay, so, once you do that you can start pruning the search space.

Because, essentially, now, you know all the adjacent countries Okay.

Cannot take the value black. Okay.

And this is what is happening. Okay.

You remove the value from the set, from the domain of these values so they can't

take that value anymore. Okay.

Now you color Luxemburg in yellow. That's the tiny pieces that you see over

there, right. And so the adjacent countries to

Luxemburg, okay, Germany, France. Cannot be colored with yellow, so you're

going to remove these values from, you know, Germany and, and, and France.

And then you're going to color Germany, let's say in red.

You're going to remove all red from all the adjacent countries, okay, Denmark,

you know, the Netherlands and, and, and France.

France is going to become blue, okay. Then you will have to choose a color for

the Netherlands and Denmark, which in this particular case are easy to do.

Okay? So, that's the way the constraint program

is going to work, okay? So, once again, so those constraints, and

I will tell you exactly the pruning that they do later on, but that's, that's the,

they will basically prune the search base the way I've shown you.

Okay, once again, the computational paradigm is using the constraint to reuse

the search space when you're stuck, okay. You basically make a choice.

The first choice that I've shown you is coloring Belgium in black.

Okay, so in the particular coloring problem, at the beginning there was no

space search reduction, there was nothing you could propagate, and I will tell you

why later on, right? And then afterwards, you know, what

happens is you give a particular color to Belgium.

Okay so you gave the color black, okay? So, when that happens, you look at these

constraints in which Belgium appears. Okay?

And so essentially these constraints can be, can be rewritten you, by replacing

you know, the decision variables of Belgium by black.

And now, what you see is that these constraints are turning into, ooh, France

has to be different from black. Ooh, Germany has to be different from

black. And those are very easy, you know,

constraints to deal with, because at this point, if you want to satisfy these

constraints, what, the only thing that you have to do, to do is say, ooh, France

can take all these colors. If France can still take the color black,

I have to remove it, because if it takes the value black.

Is, this constraint is not going to be satisfied.

So, you can use these constraints to start pruning the search base.

And that's where the constraint programming system does, okay?

So, that's what going to happen. Oops.

Look at this, so oops, I'm go back, so you give that, and you remove the value

of these variables. Okay, so once again when you think about

constraint programming, it's not a branch and bond framework.

It's called a branch and prune framework. In the sense that what you do is you

prune the search base but you don't use a bonding technique to do that.

What you do is you use the constraints to remove the value from the variables, from

the domain of the variables. And once again when you start to

decompose the problem, it's like the branching part of branch and bond.

Okay? And the pruning is based on essentially

feasibility information. You look at the constraints and you try

to remove value that cannot appear in any solution.

Okay? Remember when we discuss France to be

different from black. The color of France has to be different

from black. What that means is that, you know, we

want to, when we remove the value black from the domain of France, we know that

this is a value, is the valid inference that we can do that.

We are not removing any solution, because if France was blocked that constraint

would be violated. Okay?

So, so one of the, a couple of things that I have to mention.

You know, constraint programming is a complete method, okay?

So, it's going to find a solution if one solution exists.

It can find all solutions if you want all of them.

And if you are in an optimization problem, it will find the optimal

solution. And I will come back to this later on and

how we do optimization using constraint programming.

But one of the key things is that this, this technique, this methodology, this

computational paradigm can find optimal solutions.

Can always, there's always a guarantee that it will find a feasible solution or

the optimal solution. Of course, you know, it may have an

exponential behavior, which means that it can actually take a long, long time to

get it. But, if you give it enough time, it will

always find a feasible solution, it will always find an optimal solution in an

optimization problem. Okay?

The focus, this is the other things that I have to tell you, the focus in, in

constraint programming is on feasibility. Okay?

It's basically, you know how to use constraints to prune the search space,

okay? So it's a very different focus than

branch and bond. Where the focus is on bonding.

Is finding these optimistic evaluation. And, and is relaxation.

Here it's, it's a different kinds of relaxation, in a sense.

And what we focused on in feasibility, and removing as many values as we can

from the domain of these variables. Okay?

So, this is a, this is a way you can view a constraint programming system.

You have a search, okay, and you have a constraint store.

What you are trying to do all the time is ooh, can I study [INAUDIBLE] this

constraint, can I study [INAUDIBLE] this constraint?

Okay? And then when you start, when you say

okay, I can study [INAUDIBLE] constraint, but I cannot prune the search space.

What the search is going to do is order a new constraint.

And the constraint store is going to say yes or no.

Okay, am I still satisfiable or not okay? And so in this particular case, it's yes,

I'm satisfied, you can continue. Okay, and sometimes you know the search

is going to send another constraint, and then you say, no, no, no, no, no, no I

have violated, my constraints are violated you know give me another

constraint, okay. Remove that one and give me another one,

okay? So this is inside of a constraint

programming system, okay. So what you see there is essentially the

search base representation, the domain store.

That's essentially the domain of all of the variables.

And what you see gravitating around it are the constraints, okay?

And this is kind of interesting, right? These constraints are only interacting

with the search base. They are always trying to say ooh, can I

remove values there. Ooh, am I feasible, but we'll come back

to that in a moment. But, they don't know about each other,

and that's both a strength and a weakness, okay?

So it's easy to add new constraints, because they don't interact with the

other one. They just interact with this

representation of the search space. Okay.

So, so, so I alluded to this already, what does a constraint do.

A constraint has two goals in life. One of them is checking feasibility so

the constraint is always looking at the domain store.

The set of possible values that a variables can take.

And is always asking, ooh, am I feasible? You know, can I, can I find a solution to

myself? Okay?

So, that's feasibility checking. So, we always try to see if any one of

these constraints is feasible, independently of the other ones.

Right? So, you look at one constraint in

isolation, and you ask yourself can I satisfy this constraint?

Can I find a solution? That's the first thing you always do with

these constraints. And the second goal in life for a

constraint is to prune the search space. They're going to look at the search space

and then say can I knock down some values there?

Because then my search becomes, you know, smaller, and that's how you can curtail

this exponential growth, okay? So the second goal of pruning is

basically looking once again, you know, constraint evaluation, and saying, ooh,

to be satisfied I have to remove these values in the domain of those variables.

Okay? And that's what you do, that's what the

constraint does. You have these two things, very, very

it's checking, making sure that the note that you're exploring is potentially

feasible. And then pruning, trying to reduce the

set of values of the various variables. Okay?

I talked about this, basically you know, this is basically summarizing of what I

just said. Okay?

Of course, you only prune when you know that you are feasible.

You will never try to prune when you are already in infeasible state.

Okay? Now, the core, the core of a constraint

programming system, is the, is propagation engine, okay.

And the way to think about is it's, it's a very simple iterative algorithm, fixed

point algorithm where, you know, the constraint engine is going to take one

constraint, and say, are you feasible? OK, and if the constraint is feasible

it's going to tell the constraint, true! And so the constraint is going to prune

the search space. And then the engine is going to say,

select another constraint, and say, are you still feasible, okay?

Can you prune the search space? And the engine is going to continue doing

that with all these constraints. You know, are you feasible, can you

prune? OK, until there is no values that can be

removed from the domain of any variables. So there you reached this stable state

which is called a fixed point, right? And then you know that at this point

you've inferred as much information as you can, okay?

And so the system will typically go back to the search component and ask Ooh, make

a choice because I'm stuck at this point if you haven't found a solution so far.

Okay? So that's basically the key.

So the key is basically this propagation engine which is basically selecting

constraints asking if they are feasible, and then, if they are feasible, asking if

they can prune their search base. Okay so if you come back to this

beautiful eight queens problem, right? So my beautiful queen, right?

And so I'm basically asking so what are the decision variables.

And I told you that before, there are many, many different modelings, okay, of

any kind of optimization problems. And the eight queens problem is one of

these problems where you have many modelings.

So I'm, so I'm going to show you one of them, okay.

But there are many, many, others, and that's what makes optimization very

interesting in general, because you have to find out, you know, which model am I

going to use, is it going to be good or not, you know, and so on and so forth

okay. And we'll see what it means to be good or

not, but in a sense, it's kind of, will I be efficient, will I explore a small part

of the search space. So I'm going to show you one modeling of

the eight queen problems. And the key idea there is that I'm

going to associate a decision variables with every column.

I know that I have to place you know, eight queens.

I know that you know, the queens can not be on the same column otherwise you, they

will attack each other. So I know by definition that I can

associate a queen with every column, okay.

And therefore, the only, the, the, what the decision variable is going to do, for

every column is, is going to decide which row the queen on that column is going to

be placed on, okay? So decision variable, one queen per

column, and the, the decision variable is denoting the row for that column on which

the queen is going to be placed. Okay?

So these are my decision variables in this particular case.

Now what are the constraints? There are three types of constraints so

know that we have a queen which is associated with everyone in the column.

We have to make sure that they are not placed on the same row, otherwise they

would attack each other. And not on an upward and a downward

diagonal. Okay, so, yeah that's what I said.

Okay and so what you see here is once again a high level constraint programming

model to do that. Okay, so we basically this is for the

eight queen, so we have a range from one to eight.

Okay, That's basically the eight column. Okay, so now we have a decision variable

which is called row okay, for every one of this column I have to associate a row

with that column, and there are eight rows so that's a set of values.

That, that particular, that particular variable can take, and what you see over

here are all the constraints, and what I'm basically doing for stating these

constraints, I take two, you know, two rows two columns i and j.

Okay? And I'm basically assuming that i is, you

know smaller than j, and then I'm basically specifying that they cannot be

on the same row, they cannot be on the same, you know, upper diagonal and, and

lower diagonal. And that's what you see over here, okay?

So these are basically the constraints. And once again they are like in the

coloring. They are, you know, not equal

constraints. I'm basically saying that the row of i,

has to be different from the row of, of j.

Okay? And then that, you know, the row of i, is

different from the row of j, plus j minus i, which is basically giving you one of

the diagonals. Okay.

So these are the rows, this is the upwards diagonals that I was mentioning

and this is the lower diagonal, okay? And I do that for every pair of queens

you know, ordering them by you know, I take i and then I take j, which is

greater, okay. So when you have that what you may wonder

is, you know, what happens when I give the value one to a popular queen?

When I place, you know, the queen on column one to row one.

Well these are essentially, what you see there, are essentially all the

constraints. Okay?

I just explained that model here into this set of constraints.

When you give the value one to the part of the row, so this is the expansion

right, so this is not on the same row. This is not on the same diagonal, this

upward diagonal. This is not on the downward diagonal.

Okay? And so now, if I give the value one to

row one, what's going to happen? Well, this is, this constraint is

going to become you know, row two has to be different from one.

Okay, so you will make sure that the second queen, the queen on the second

column, okay, cannot be placed on row one.

That's what this constraint will do. The next constraint that you will see

here is going to say that, you know, row two is different from row zero.

That's not useful because we know that zero is not part of its domain.

And the last one here is basically going to tell you that row two has to be

different from two. That is essentially, the diagonal that's

going up there, right? And so, well, it actually, it depends the

way you see this, the, the test. But it's basically saying that it cannot

be placed on, on the second row, on the second row, okay?

And you can use that for removing the search base from that value from the

domain and therefore reducing the search base, Okay?

Once again I told you that the two things that it does is visibility checking and

pruning, OK. Lets skip this slide but what I want to

do here is basically telling you a little bit How this is done for the very simple

constraint that we have considered here. For the map coloring and for the, the,

the queens the, the, the queens problem. Okay?

So, essentially we'll consider two variables, x and y, and we going to say

that x can take the value between zero and two.

And that y can take the value between one and three.

Okay? Typically what we do and in many of

lectures that concern programming that's what I'm going to use.

We are basically saying that x, the variable x, has this domain, zero, one,

two. And that y has this domain, one, two,

three. Okay?

And so, the domain essentially is, the domain of x okay, is going to be

represented by dx, is a set of these values, okay?

And so one of the goals is going to be trying to knock down values from this

domain all the time. Okay?

Sometimes I'm going to use intervals as well to denote you know, 1 through 5.

To denote the value one, two, three, four, five.

Boring, right? So, but this is a notation that I'm going

to use from time to time. Okay?

So, let's look at the constraints. x has to be different from y.

Okay? So, that, that constraint, and assume

that the domain of the variables are this.

Okay? So, one of the things that I have to do

is to do feasibility checking. Is this constraint feasible?

Obviously here I can see that it's feasible.

Right? I can take zero there and three there,

and it's going to be feasible. Okay?

So, the general rule here is that what you do is you basically take the union of

these two domains. Right?

And, and you look, if the size of that union is greater than one.

If it's greater than one, okay? So what that means is that I can take at

least two values. Okay?

And therefore, you know, I can, I can, the constraints is going to be feasible,

okay. So in this particular case, I can see

that you know, the size of this thing is four, the union of that is obviously

greater than one, and therefore, or greater or equal to two like I'm writing

there. And then you are sure that this

constraint is feasible. Okay?

So, this is all, so feasibility here is going to be very, very simple to to

achieve. now how do we do pruning.

This is what I've shown you before. Right?

So, essentially the pruning in the examples that I've shown is happening

when the variables can take only one value.

Okay? If it has two values, essentially you

can't prune. It happens only when a variable has only

one value that you can start pruning the search space.

If a variable can take only one value, you have to make sure that the other

variable cannot take that value, and you remove it.

And of course that's, you know, that's symmetric whatever the value is.

Whatever the variable is,it will go from one direction to the other, or you know,

from the first variable to the next one. Okay?

So if Y is, if Y is to have the value two, you will remove two from the value,

from the value of x. Okay?

So that's how you do pruning. Now this is very, very simple, right?

So this is a very, very simple constraint.

One of the beautiful thing about constraint programming is that

constraints can be arbitrarily complex. And we'll see examples where the

constraints itself is an optimization problem and you still can use polynomial

algorithm for actually pruning the search spaces and we'll go into that, okay.

So this is a really, really tiny example to show you the principle feasibility to

checking pruning, but we'll see much more interesting examples with feasibility

checking and pruning I'm going to use very interesting algorithm.

Okay? So, see you next time.

This was the first lecture on constraint programming.

There will be many more to come, with many more interesting things.