0:00

Welcome to workshop nine, this is the first workshop

of the course on solving algorithms. >> Okay,

workshop nine is about preparing medicinal herbs.

We saw in chapter four how Shennong was able to resolve the curse issue in the village.

And then no more new kids, they would be become ill again.

But then there are already a whole bunch of boys and girls that are already sick.

So Shennong will have to prepare some herbs to heal these children.

There are different kinds of herbs including ginseng, poria, angelica and

so on.

And then there are different steps for preparing these herbs as well.

Steps including cutting, soaking, brushing, bleaching, and so on.

There are different steps for preparing different herbs, and

the ordering could be important.

For example for preparing ginseng, it could be cut only after it is bleached.

And then also the different steps they might have to utilize, certain tools.

We would have a pottery knife, we would have iron knife,

and the gold knife as well.

But then some of these steps they require the same tools

and in that case, those task which are sharing the same tool,

they cannot overlap. >> Yep.

>> So what's the objective,

what is the goal of Shennong? >> Of course,

Shennong wants to get it all over and done with as quickly as possible,

right? >> Sure, certainly.

>> We want to get all the tasks finished,

which is a usual objective we have when we are doing scheduling kinds of

problems. >> So

should we look at the MiniZinc model? >> Yep,

let's have a look at the MiniZinc model.

So if we open the project file attached to this workshop,

you should pop up a window like this.

And we can look through our MiniZinc model.

So here's the data, of course.

We've got n as the number of tasks, and for each task, a duration.

We've got m which is the number of precedences.

And there's already two arrays here, the pre and the post array.

And we're basically requiring that the pre task finishes before the post

task starts. >> So that's the standard way of

specifying precendences. >> Exactly, we've seen that in plenty of

other examples in this course. >> And

then we've got a number of disjunctions.

So we've got O disjunctions and each of these disjunctions is a set of tasks and

none of those tasks can overlap. >> So we have an array there,

and each array element is a set. >> That's right.

>> A set of tasks.

And all the elements of this set they cannot overlap

with each other.

>> Exactly. >> Right.

>> All right, and so then the principal

decisions are these usually in scheduling problem is, when do we start this task?

Alright, so there's the start time.

But we've also got another version of those decisions here.

The end time, right?

So this is the start time plus the duration, all right?

And obviously these are tightly tied,

if I fix all the start times, I'm obviously going to fix the end times,

because the durations are known.

But if we could also fix the end times, and then we'll fix all the start times,

right? >> So that means we only have to decide on

one set of these decision variables. >> Exactly, alright, so

let's look at our model of the problem.

So here's our precedence constraint, that's pretty straightforward.

We're just saying the end time of the pre-task is less than or

equal to the start time of the post-task.

That clearly means that the first task finishes before the second task begins.

Then we're going to do something interesting,

we're going to introduce some new decision variables, b.

Okay, and this is between pairs of tasks.

This is going to keep track of the relative ordering of pairs of tasks.

But now we only care about pairs of tasks which are in disjunction, alright.

We only care about the relative ordering, so which one's before which one.

In the case that they can't

be at the same time. >> Okay.

>> Alright, so the first part of

this here is basically setting all of the Bs that we don't care about to 0,

because we're never going to worry about them.

Alright, so we don't care about a B, if we have two tasks T1 and T2.

If T1 is greater than or equal to T2, we don't care about it

because we'll always think of the task pair IJ in the order I less than J, right?

So if not the other way, not J, I. >> Okay, so

the reason why we need to have this constraint is because we are defining

a big two dimensional array of Bs, and for every pair of tasks.

But then if the two task,

they are not within a disjunctive relationship then we don't care.

So we would like to set those B's to be 0. >> Yeah, and also for every pair, right,

we have two variables.

So we also want to get rid of half of them.

So this gets rid of the half we don't care about.

And this other test here is, if there's no disjunction where these two tasks appear.

So they can overlap with each other in any way,

then we're just going to set this boolean to 0, since we don't care about it.

Alright, so the real purpose of these booleans is for this constraint here.

So we're looking through every one of our disjunctive sets.

We're taking any two tasks from that disjunctive set where T1 is less than T2,

because we always look in that order

and we say this boolean, t1,

t2 is true means that task1 finishes before task2 begins, right?

And since they're in disjunction,

if that's not the case, then it has to be the other way around.

And so if it's false, it means that task 2 finishes before task 1 begins.

>> Okay, so

in some sense this boolean variable is used to indicate whether a task

should finish before the other one. >> Exactly,

the tasks that we care about. >> Right, sure.

>> So the ones in disjunction.

Alright, finally we're looking at the makespan which is just the maximum end

time. >> Yeah.

>> Right, and then we're going to minimize

that makespan, right? >> I can see that you have already

prepared. >> Okay, so we've prepared because we're

going to have to, well, we've got three choices for variables to put here, right?

We can take start times, or end times, or

the boolean variables. >> Wow.

>> And we have four choices to put for

var selection.

And let's say four choices to put for

value selection. >> So input order is?

>> Input order is just, we try them

in the order they appear in, right? >> Right, and

first-fail is to select the variable with the smallest domain, so that if you-

>> At the current time.

>> Yeah, at the current time.

>> Yeah, and smallest, remember, looks for

the variable which has the smallest current value left over

in its current domain. >> And

largest is just the opposite.

>> Exactly. >> Right.

>> Then indomain_min is setting it to

its minimum value, its maximum value, the median is in the middle.

It's not likely to be very useful for scheduling.

And random, which just seems like a totally bad idea, but

it's often not as bad as you think. >> Right.

>> Alright,

so let's just start off with a very straightforward input order.

We're just going to fix the variables in order indomain_min.

Sort of almost a default kind of search strategy,

if you don't think about anything at all.

Let's start with our simplest example here, and run our model, all right?

So notice one thing, we've got the statistics coming out here,

we've gone into our configuration.

We've actually turned on statistics for solving, and

also, because later on we'll run some examples which take a while.

We've added the silver flags and we've got a time limit of 6,000 milliseconds, or

6 seconds.

Just so that we don't spend a lot of time staring

at the screen. >> Yeah, really depends on how much time

you have for your experiment. >> Exactly, exactly.

All right, so we can see that we found a solution fairly quickly.

12 failures, so indomain_min

is a sort of obvious thing right? >> Yeah.

>> Because we're tring to minimise,

what if we do indomain_max? >> Yeah.

>> Let's have a try and see what happens.

Alright, so I don't know if you saw it flash past,

but we found a lot more solutions on our way to the optimal.

And if you look at the phase, let's say 39 verses the previous one was 12.

>> A lot larger.

>> Exactly, so

really indomain_min was much better than that, right?

What about if we try >> Yeah.

>> if we try indomain_median, so

we're going to set it to a middle value.

Alright,

so if you can see we've got a few answers, >> Mm-hm.

>> 48 failures, which is sort of worse,

in fact, right?

So really setting it to the middle of your range in a scheduling problem is pretty

bad, right?

Because you're not going to learn very much from that.

>> Let's try random as well.

>> Let's try random.

Of course with random we could be super lucky.

So 23 is actually not too bad, it was better than medium

and better than max which was possibly the opposite,

and not as good as min. >> Min is still the best.

>> Yeah, well,

because we're trying to minimise makespan. >> Exactly,

yep. >> Exactly, all right,

what happens here, we'll go back to min.

14:05

So you can immediately notice right,

before we even hit the timeout that we've got way better solutions, right?

Our best solution we found was 642 which was way,

way better. >> Two times better.

>> Than the one that we got out of

the booleans.

And this is where we're seeing so, there's a kind of contrast here.

There's two things that we can be aiming for.

If we're aiming to get the best solution quickly, then actually this

standard scheduling approach, smallest variable, sort of pack them in,

gives you very good solutions quickly. >> Right.

>> If we're aiming to prove optimality,

actually, the search space for optimality is much,

much smaller if we search on the Booleans. >> Right.

>> Alright, so

it depends on the size of your problem.

And of course and actually, we can actually build much more complicated

search strategies, but not directly.

You'd have to do it directly in the solver,

we can't do it through MiniZinc at present.

Where we would actually sort of combine these two things.

We would want to be searching on the B variables, but

searching in order to find the small values as quickly as possible.

And that's how modern scheduling approaches are actually done.

>> That's surprising but I suppose

our learners, they should try all the experiments. >> Well, yes-

>> There's three types of variables to

search on.

Four kinds of variable selection, and then four kinds of value selections.

All together, 48 different experiments. >> Yes, all right.

So you'll need to do some scripting if you really want to do this fully.

And indeed you may find you can do better.

That's definitely the case if you put the end time there.

And that can be sometimes very competitive to the start time.

Alright, but, remember we were doing this on this model.

We have an improved model, right?

Because now we remember about global constraints and

this non-overlap constraint is exactly a disjunctive constraint.

So why didn't we model the model this way?

There's been a more natural way once we know about the disjunctive.

>> Exactly.

>> Right, so we look through all of

our disjunctive sets.

We just have all the start time for

all the tasks in that disjunctive set and all the durations

and then we just call disjunctive. >> We do

not have the boolean variables anymore. >> We do not have the boolean

variables anymore.

So is this better?

Well let's run on the same data files. >> Right.

>> So remember our,

so we've got the search space here, is the standard search strategy, right,

with s in domain_min.

So it's the same one we're doing before. >> Yep.

>> And, right,

we're actually not going to get as far

on this particular example, yep. >> Okay.

>> So we got to 682,

this is before we actually got to 642, I think.

Yeah, so for that particular example it didn't work.

Now when we would hope that the disjunctive actually understands more

about the problem, right?

If we go back to an earlier one and run that so we can see,

okay that's number five.

We've got 7 failures, 0.115 seconds, if we run prepare, and

just check we're doing the right search.

17:01

Okay, you can see you remember, five was really a bad example for

our search, right?

It got trapped, it got stuck.

It found 39, which is probably the optimal, but it couldn't prove it,

alright, versus the disjunctive.

So you can see the power of the global inaction.

>> So in general,

the global constraint should be able to help solve the problem a lot

more efficiently. >> Exactly,

although sometimes we could be lucky if we just look at one example.

We may not get a better first solution or a better solution in a particular time.

All right, so

if we look back over the kind of questions that we are meant to answer.

The kind of potted answer we'll say is, okay, what's the best thing for

finding a first solution?

Well, and basically, you can go in any order you'll find a first solution

directly, particularly once you have the disjunctive constraint in.

What's the most complete?

So obviously searching on the boolean variables

gave us the most complete search, right? >> Because you can prove optimality.

>> Yeah, it's basically the search space

becomes smaller, because actually all we need to know

to solve this problem, is the relative order of these disjunctive tasks.

Once we know that then the rest is very simple to work out.

Okay, so search space how many failures to find the optimal solution again

goes to the boolean variables.

Right, because it just makes the search space so much smaller.

But when we want to find the first solution,

to how good the first solution is, the booleans are terrible at that,

they have no idea about the objective.

Right, whereas our smallest very quickly gets us a good solution, often it was

the best solution was first, right? >> Because the boolean variable is only

deciding on how they don't overlap. >> Exactly.

>> The direction of the precedence.

>> It doesn't know anything

about the objective at all. >> Right.

>> Right, and

if we look at robustness, how good a solution we've got in a fixed time.

So we were doing six seconds, then you can see again there was this

standard scheduling approach, which was much better than the boolean approach.

>> Smallest, and in domain_min.

>> Yeah, yeah.

Alright, so that brings us the end of this workshop.