Welcome to the module summary for module one of course three.
Jimmy, what's been happening in the story?
>> Well, a lot have happened since the last two courses.
Although [INAUDIBLE] our hero was a wise person,
his curiosity got the best of him this time.
One night he couldn't help but to mess around with a magical tablet and
accidentally broke it.
And the leak energy from the cabinet creates a chaos n space and
time, and chugolan was actually sent back
to to the beginning of time to fix the problems that he created.
So we saw Chugolan helping Yuwa to pierce the holes in the nine heavens,
we also saw Chugolan teaming up with Chan Dong.
To help fix the cause issue of vidich actually creating The 100
[INAUDIBLE] magical prescription for mankind.
>> Mm-hm.
>> This is actually this module talk about how a CPU software works.
>> Exactly, so we've looked inside the CPU software and
we've looked at two sort of key components of a CPU software.
Which are the domains, how we represent variables and
what choices they have left over.
>> Mm-hm.
>> And propagators, which is how >> Constraints are used to infer or
remove values from these domains.
So we get less possible values.
>> Right, so property is really the only way we
represent constraints in the constraint programming software to do inference.
>> Exactly, the only thing that a constraint programming software knows
about a constraint is the propogated implements the inference for
that constraint, and nothing else.
And then those inference would help me move possible values from
the domains of variables.
>> Exactly and that's what stopping us doing our brute force search.
So propagation engine, we then looked,
which is the loop which is handling many many times running through propagators.
And we so looked at, >> The properties of that engine,
which will make it efficient.
Because we're going to run all these propagators millions and
millions of times.
>> Sure, but propogation is not the only thing that we would do
when solving constrained programming problem.
>> That's right.
With just propogation we're going to solve almost no discrete optimization problems.
>> We need to add search.
>> Search is like guessing a value for each of the variables?
>> Exactly.
>> So it sounds very, very naive.
We're just going to guess a value for each variable, and
then we're going to do more propagation, all right?
But it makes a difference which values we guess.
So we talked about the variable choice in a basic search, which variable should we
guess for next, and a value choice, so which value should I give that variable.
>> When we talk about searching, I think we talk about enumeration.
But actually in most of the modern solvers, they are doing binary branching.
>> That's right, so almost all solvers just branch in two ways,
either do something or the opposite of it.
Because that actually can mimic any of the valuation kind of branching that we
also talk about.
So that's much more easy to implement and in the end, much more efficient.
>> And then we also talk about how we could do all the searching
[INAUDIBLE] as well.
>> Exactly, so finally we exposed to you how you can actually control the search of
a CP solver from the [INAUDIBLE].
>> Mm-hm.
>> We can talk about the workshop as well.
>> Exactly, so in this workshop, what are we doing, Jimmy?
>> Well, [INAUDIBLE] helped resolved the curses of the village, but
some of the children, they already sick.
>> Yeah. >> So [INAUDIBLE]
will have to prepare some herbs to heal these children.
And then for each of the particular herb, there will be different processes
using different tools to prepare them >> Because of the different processes,
we have the standard precedence constraint,
because some of the processes must be done before the other ones.
We also have the standard non-overlapping constraints, in case two processes,
they're sharing the same two.
Then they cannot take place at the same time.
And what do the learners have to do in this workshop?
>> Well, different from other workshops.
We don't want you to build the model.
In fact, we're going to give you the model.
It's actually a very standard scheduling model.
But what we want you to do is search for the right search [INAUDIBLE].
How should you do the best search on this model in
order to find the solutions as fast as possible?
So they do not have to build a model, but
there will be a lot of experimentation to do.
>> Absolutely, there's three different variables we can search on.
>> Yeah. >> And
then there's lots of different searches we can try.
And basically, we want you to explore as much as you can
which of the searches are the best over a wide variety of different instances.
So by search you mean selecting the right variable choice and
also selecting the right value choice.
>> Exactly.
>> Wow. >> Exactly.
And that's what what we've done in module one of course number three.
Prof. Jimmy Ho Man LeeProfessor
Prof. Peter James StuckeyProfessor
