Welcome to the module summary for module one of course three.
Jimmy, what's been happening in story?
Well, a lot have happened since the last two courses.
Although Zhuge Liang 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
the magical tablet and accidentally broke it
and the leak energy from the tablet created chaos in space and time and
Zhuge Liang was actually sent back to
the beginning of time to fix the problems that he created.
So we saw Zhuge Liang helping Nuwa to patch the holes in the Nine Heavens,
we also saw Zhuge Liang teaming up with
our Shennong to help fix the curse issue of the village,
as well as actually creating the 100 herb magical prescription for mankind.
This is actually this module talk about how a CP solver works.
Exactly. So we've looked inside the CP solver
and we looked at the two sort of key components of the CP solver which are the domains,
how we represent variables and what choices that have looked over,
and propagators, which is how
constraints are used to infer or remove values from these domains,
so we get less possible values.
Right. So propagator is really the only way
we represent constraints in the constraints programming server.
Exactly.
To do inference.
The only thing that a constraint programming solver knows about a constraint is
the propagator that implements the inference for that constraint and nothing else.
And then those inference would help remove possible values from the domains of variables.
Exactly. And that's what's stopping us doing our brute force search.
So a propagation engine we then looked at which is the loop which is handling many,
many times running through these propagators.
And we sort of 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 propagation is not the only thing that we will
do when solving a constraint programming problem.
That's right. With just propagation,
we're going to solve almost no discrete optimisation problems.
We need to add search.
And search is like guessing a value for each of the variables?
Exactly. So it sounds very,
very naive we're just kind of a guess a value for each variable,
never going to do more propagation, 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 the value choice, so which value should I give that variable?
When we talk about searching,
I think we were talking about enumeration.
But actually in most of the modern solvers,
they are doing binary search at branching.
That's right. Also all solvers just branch in two ways are they do something,
or the opposite of it because that actually can mimic
any of the valuation kind of branching that we all talk about.
So that is much more easy to implement and in the end much more efficient.
And then we also talk about how we could do all these searching in MiniZinc as well.
Exactly. So finally we exposed to you how you can
actually control the search of the CP solver from the MiniZinc level.
We can talk about workshop as well.
Exactly. So in this workshop, what are we doing Jimmy?
Well, Shennong helped me solve the curses of that village.
But some of their children, they are already sick.
So Shennong 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 process they're sharing the same tool,
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 strategy.
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 they'll 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 a search, you mean selecting
the right variable choice and then also selecting the right value choices?
Exactly. And that's what we've done in module one of course number three.