CP 2 - propagation, arithmetic constraints, send+more=money

Loading...

From the course by The University of Melbourne

Discrete Optimization

254 ratings

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

The University of Melbourne

Discrete Optimization

254 ratings

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

From the lesson

Constraint Programming

Constraint programming is an optimization technique that emerged from the field of artificial intelligence. It is characterized by two key ideas: To express the optimization problem at a high level to reveal its structure and to use constraints to reduce the search space by removing, from the variable domains, values that cannot appear in solutions. These lectures cover constraint programming in detail, describing the language of constraint programming, its underlying computational paradigm and how it can be applied in practice.

CP 1 - intuition, computational paradigm, map coloring, n-queens27:15

CP 2 - propagation, arithmetic constraints, send+more=money26:20

CP 3 - reification, element constraint, magic series, stable marriage16:48

CP 4 - global constraint intuition, table constraint, sudoku19:22

CP 5 - symmetry breaking, BIBD, scene allocation18:29

CP 6 - redundant constraints, magic series, market split11:35

CP 7 - car sequencing, dual modeling18:19

CP 8 - global constraints in detail, knapsack, alldifferent33:43

CP 9 - search, first-fail, euler knight, ESDD25:48

CP 10 - value/variable labeling, domain splitting, symmetry breaking in search28:45

Meet the Instructors

Professor Pascal Van Hentenryck
Dr. Carleton Coffrin
Adjunct Lecturer
Computing and Information Systems

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.

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.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play