0:00

Welcome to Workshop 10.

This is the second workshop of the Solving Algorithms Course. Jimmy, what's happening?

Well, in this new workshop here,

we are preparing our chemical potions.

We saw that Shen Nong had already prepared the herbs.

And the reason he had to do that was to make chemical potions to heal the sick children.

Okay. While there are different potions to make,

but the ordering of preparing the potions are important because some

of the potions would be used as ingredients to prepare other potions.

Yes.

So, we have precedence constraints again.

Yes.

Okay. And then, Shennong could not do all the work by

himself so he has to hire a bunch of alchemists to help him.

So, everyday, Shennong will have to prepare some potions.

There is a maximum number of potions that he could do

everyday because there's a limit on the equipment that he's got.

Yes.

There is also a least number of

potions that he would like to make because he would like to

keep the alchemists that he's hiring busy.

Yes.

But then, so, he's going to hire a bunch of alchemists.

Everyday he would like to deploy a minimum number of

alchemists to keep them busy again because he would like to get his money's worth.

Yes.

But then, there's a capacity constraint on the size of the workplace.

So, he could only put a maximum number of alchemists into the workplace.

Yes.

Okay. Now, so, of course,

Shennong would like to save some money,

so he would like to minimise on the maximum number of alchemists

that he will need on everyday across all the days in this preparation process.

Right. Basically because he has to hire alchemists for the entire period.

Yes.

So, he's paying for the maximum.

Yes.

Alright. So, let's have a look at the model.

So, the model here is a bit different from other models we've seen in this course.

Alright. So, here is a reading in of the data.

Alright.

Right. So, reading in the number of potions,

how many alchemists each of them need,

a minimum or maximum number of potions we have to make on each day,

and minimum number and maximum number alchemists we have to use on each day.

Yes.

And the prerequisites between the potions.

Right.

Right. Here is a two-dimensional array. Alight.

Okay. But here, we've got three different ways. Alright.

So, we've seen in multiple modeling in

previous courses that we can often model things in multiple different ways.

So, here, we're going to model them in three different ways.

And all the constraints are going to be there in three different ways.

Okay.

Okay. So, the first way is for every potion,

we just decide which day do we do that on.

Right. That's the basic.

That's a fairly easy way of thinking about it.

We can also for every potion if everyday, we can have a zero,

one variable or a true-false variable effectively saying,

do we make that potion on that day?

Yeah.

Okay. Which is often what we do

if we're trying to write a MIT model for doing this directly.

Then, another way of thinking about it is,

on everyday, what potions do we make?

Right. Which is a set of potions.

So, we decide the set of potions we make on each day.

So, this is a standard technique when you're modeling a rostering problem.

Yeah. Exactly. Alright.

So, we got some auxilliary variables just to count stuff.

So, how many potions do we make on each day?

That's number. And how many alchemists are working on each day?

Alright.

That's another one. And then,

there's our objective, which we're trying to minimise.

Okay. So, let's look at some basic constraints.

Okay. So, we need that the number of alchemists

working on each day is less than or equal to the objective because that's

just maximising saying the objective is the maximum number of working things.

Right. Then, we need the potion prerequisites.

Now, that's pretty easy with the day variables, right.

So, we just say, "Okay.

This is the one that has to be finished first.

Then, it has to be on a day that's before the day where we do the second one."

Okay. We can also map it using these Boolean variables, right.

So basically, this is calculating the day when the first one was done,

and this is calculating the day when the second one was done,

and making the same constraint and it ends up being a linear constraint.

Right.

We can also do it with set variables.

It's a bit trickier. Right. So, we're basically saying, Okay.

If we look at all the days and we have that this potion is done on day D1, right.

And then, if we look at all the days before D1,

then we can't have the second potion done on that day.

In this way of expressing the constraint,

we're using if then.

Yes.

And we're also using negation.

Well, yeah. Negation of a Boolean isn't too bad.

Okay.

Okay.

Yeah.

So, it's bad, but it's not too bad.

So essentially, we have three different ways of making use of

the three kinds of decision variables to express the constraint.

Yeah. The prerequisite constraint.

Right.

Right. So, they are all there at the moment.

Yes.

Right. And we're going to do that for every one of the constraints for the problem.

Okay. So, we have to keep track of the number of potions we've made on each day.

Yes.

Right. So, we can do this by just summing up for every potion,

right if it's made on that day.

Yes.

Okay. So, that's obvious way of doing it.

Very similar if I've got the Booleans,

I'm just summing up the zero,

ones of which potions are on that day.

Yes.

But if I have the potions, right,

which actually gives me the set,

I just need to get the card number.

Right.

Right. So, it's simpler. This is simpler in the set view.

Alright. What about the calculation of how many alchemists are working on each day?

It's very similar as to what we did before.

Right. Here, we're just saying, if we do this potion on this day,

then we have to have at least this many alchemists that potion needs.

And that gives us the total working on that day.

So, I'm summing across all potions.

They are very similar in the Boolean view.

Right. It's just that this expression here,

day of p is equals d is exactly equivalent to this potion of p potion_day p,d.

And for the set view,

we can actually make use of a global constraint,

which isn't normally visible, but is available.

And this is basically something which given the set and it says for each of the elements,

so the potion is the set of elements and Alchemy is the weight of each element.

It's going to calculate the weight of the elements in that set.

Wow.

Okay. So, this is exactly what this global constraint does.

And we're going to need to have

this definition here just to make sure that it gets through the flatzinc.

As a predicate.

Exactly. That the solver Gecode understands this constraint.

So, in this exercise here,

we can really see the power of multiple modeling, right?

I mean, it allows us to look at the problem from different viewpoints.

Exactly.

And you can also see that some of the constraints are

easier to express in a particular viewpoint.

Exactly.

Right.

Alright. So, then we got some more constraints.

So, this is potions are not assigned to two days.

Okay. So, that's obvious in the day view because the day view,

I look at the potion, it's given a day, can't be given two day.

Exactly.

So, that always happens. Not obvious for the other one.

So, for the Boolean view, well,

I sum across all the days and I say

the number of days when I make this potion has to be equal to one,

which means only one day can be true.

And for the set view,

I basically need that the sets,

right, for each day, and it'll have to be disjoint.

So, that's this global constraint all disjoint.

So, a potion cannot appear in more than one set.

Exactly.

Yes.

Basically, two sets have to be disjointed.

Alright. Now, remember,

we've got multiple viewpoints, so we have to make them agree.

Yes.

So, if we're going to use two viewpoints, we have to make them agree.

We can channel between day and potion day.

Yes.

And this is basically exactly the statement we said, potion_day p,

d is exactly the same statement saying the day that I made potion p was d.

Yes.

Right.

We can channel between potion day and potion view which is almost the same.

If I made potion P on day D,

then it was P in the potions that are made on day D. And

for this set view and assignment view,

then we have this int_set_channel which does exactly that.

Global constraint?

Exactly, because this is a common thing that happens in modeling.

So there is nothing wrong with not having global constraint here because in fact,

there's not much you can do better than these definitions.

Sure.

Okay. But also, in order to make our model strong,

we're going to add some redundant constraints.

So here is just making sure that if we add up all the amounts of working on the days,

it gets the total Alchemy we need to do,

which is the sum of the Alchemy of all the potions.

And basically, if we add up all the numbers,

we have to get to the number of potions.

So it's basically just redundant constraints.

Here is a tricky one,

and this is looking for every day.

We're sort of looking at the number of potions that are made after this day,

and we're saying, "Well,

that total amount of Alchemy that we're going to

use after this day has to be greater than or equal to the number of

days left times minimum number of alchemsits we can use every day, and it has to be

less than ir equal to the number of days

left times the maximum amount we can use which is the objective."

So it's basically a redundant linear constraint but let's just look forward to say,

"Well, if all of these potions are still unassigned, they still have to be done.

And if that ends up being too expensive in the future, then I can just stop."

My understanding is that a constraint is redundant if it's not going to change our solution.

Yes.

So essentially, in terms of getting a solution,

the redundant constraints are not needed.

But we will put them here if they can help us to increase propagation.

Yes, exactly. So we don't need any of these constraints

marked redundant we can remove and that's part of this workshop.

You are allowed to remove all things which are marked redundant.

Okay. We've got the day view.

Then we can do the same thing with

the potion day view and with the potion view although notice,

they are not so clever here,

we're actually making use of the fact that we can write down something directly.

The day of this potion is after some day.

And that's just a very simple Boolean.

Here, I have to calculate an expression, so it's not so direct.

Okay. So now, we have this complicated task, Jimmy.

We have to work out the best model and the best search at the same time.

So how on earth are we going to tackle that?

Now, first of all, this model would work.

Yes.

You're combining everything together. It would work.

Let's run the model, that's a good idea.

It better run. Otherwise, something is wrong.

I hope.

I can't spell indomain_min, so that's what's wrong with that.

So that's okay. Line 134.

Search one.

There you go. Okay. That's too bad.

Oh, okay.

Alright. Let's try again. Live action.

Okay. Yeah, it works.

We should probably turn on statistics and why don't we also put

a time limit of 6,000 milliseconds so that we're not waiting too long?

Alright. Okay. So now,

we can actually get some statistics out of this.

You can see that we found this first solution is fairly straightforward.

We can get a solution in 17 failures.

Okay.

Alright. So currently, by the way,

our searching, we're doing is we're just using the day variables.

We're going in order and we're setting with the minimum values,

kind of like very just naive.

The good thing about this search is it doesn't care about the constraints.

It can't be changed by the constraints.

Basically, we're always just taking next variable,

saying to its minimum value.

So basically, we fixed the order of the search independent of the constraints. Okay.

Let's talk about the model again.

Exactly.

So right now, we have a combined model combining constraints and

variables from three different viewpoints and then they channeled together, so they work.

Yeah.

So in essence, each of the viewpoints that the variables and the constraints,

they are redundant with respect to the other viewpoint.

Yeah.

So we could actually comment out one of the viewpoints and see how things would be like.

Yeah. Actually, why don't we just comment out everything except for the day view?

So that's the primal view,

the most obvious way of writing it.

So we're only commenting out the constraints.

We'll leave the viewpoints, the variables there.

We'll leave the viewpoints. So basically,

we're keeping everything here which talks about the day view,

and we can leave it doesn't matter,

the day view doesn't need any of these.

We don't need any channeling.

Why not?

Well, if you've got one view leftover,

there is nothing to channel between them.

Right.

I mean we could leave channeling in just to fix the variables.

Exactly.

But in some sense, this way,

we just leave the variables free and we're done.

Okay.

So then they'll just be set to arbitrary values.

Really should have thought about easy ways of commenting this out quicker

because we're going to have to comment back in at some point. Alright.

So if we had before with all the constraints,

we ran the search shouldn't change.

So we're hoping to get the same number of failures. But we've changed.

We might get more failures now because we

actually have commented out something that might be helping.

For this tiny example, no more failures.

If we look this time went down quite a lot. Well, no, not really.

Because it's a small example.

Exactly. The propagate is 11,000.

This propagation's 9,000.

Let's try it. That's a really tiny example.

Let's try a bigger example now.

Okay. So Alchemy one, running.

We cannot actually prove optimality with this example.

So can we do better.

If we went back to the original problem.

And if I can load that in,

I have a copy sitting around so I don't have uncomment.

But I need to set up the search to be the same.

And currently, we're doing int_search, day,

input_order, indomain_min and useless

complete. So if we run this one.

20:37

Run that, okay, 87, okay?

The same search base.

So now we just got to look at, okay,

let's say propagation is 22,000 for this one, point 019.

So, the big model which was this one had stacks of propagations 115,000.

Right? With point 104.

It's faster?

Yes. So our new model is faster.

So, less propagations even in this one and slightly faster I think.

Yeah I think so.

Yes it is slightly faster.

Slightly.

Okay. So, that seems like a,

once we got a good search strategy now we can sort of compare these things better,

because we know that they're finishing off, right?

Right.

And what other search strategies can we try?

Alright, so we haven't tried searching on the potions view.

Right.

Right, of course if we can't,

because we've, if we change this search strategy,

let's copy this, because this thing only has the day variables left.

So there's no point comparing with that.

What we need to do is put it here, right?

So remember this have got the potion views left.

This is our optimal model,

or our best possible model,

where we've kept the best version of the constraint.

And we'll compare that with the base model where we kept all the constraints.

Every version of every constraint.

And we'll see how we go.

So we try the base first.

Okay, so the set search isn't doing so well on this version, right?

It ran out of time. I think it got the optimal.

30 was the optimal as I recall.

Yeah, but it couldn't prove optimality.

Let's go to our optimised version.

Okay, so it's going to have basically the same behavior.

Yeah.

So here, for this example definitely the day base search was better.

Alright.

We can come back and look at some different things.

What about doing a search on the potion days, right?

How does that compare? And of course to do this properly we should actually,

we should actually try everything and set up big scripts et cetera et cetera.

We'll leave you to do that.

Too many possibilities.

Yes exactly. Okay. Actually we can't really compare our optimised model,

remember we've got rid of the potion day variables.

We can at least try the,

we can try the base with this version.

Right? And, well, we can getting about at the same point.

Not really helping us. Okay. Oh, yeah.

So, no different, right?

If we can't prove optimally let's just go back to two, which was maybe easier.

Maybe we can prove optimally.

No, not with this search.

Alright, the problem is now with the Booleans we've got nothing.

At least with the first fail we're actually taking advantage of something.

Alright, but let's look at this one,

which is, I've searched a bit around and this was the best one I could find.

That's sequential search.

Okay, so think about this.

We can use sequential search and also we can use Dom W Degree,

which remember is our failure base search.

So here our search says,

we're going to first search on the objective.

So we're going to sort of assume that we can get a minimum value.

And that really means that this is just trying to

find a solution which actually fits the objective.

We're using dom w degree so we are going to concentrate on variables which cause failure.

And here we're just using random values, right?

Just put them in random things because in some sense,

once we fix the objective it's sort of packing potions into boxes to make them fit.

Alright, if we try that. This is our base version. Okay?

Wow.

Okay, we can quickly find optimal solution there.

What if we do the same thing on our new search version?

Alright.

And hopefully now we can compare these two.

24:57

Alright. So that one was 117 failures.

Wow.

Okay, 26 failures. Okay? So, this.

No, seven.

Seven failures. Okay. Alright.

So it turns out that if we try,

and we should be able to try most of these things,

that we'll get very very quick answers out of our optimal model.

Right. Well, that went to go up.

Okay, but still was able to prove optimality if we go back

try the same search on our non optimised models.

So remember it's the same search, it's faster.

Okay, in this cases you can win and lose because they're dynamic searches, right?

So, but I've done a bit of looking

around the benchmarks and remember there's a whole 100 other benchmarks,

which are bigger and at least this was the best search that I could find.

I have a feeling that our base model involving all three viewpoints in there,

it might not be the most efficient model,

but it could be the most robust.

Yes, exactly. Because we're going to get the most amount of propagation.

Exactly.

Right, because it has the most constraints in it.

The question is do we ever lose some propagation?

And it is the case I've checked on a tiny example,

that our slimmed down version where we just keep the potion and the potion,

day variables actually can lose some propagation,

but it's, the payoff is that it wins.

Unless of course, this is the problem about comparing dynamic searches, right?

So sometimes the dynamic search can just win big.

Yeah.

But if you look across the average results,

then this was the best search we could find.

Alright, and if you take that and run it on the bigger examples,

and you'll need a good search to run on the bigger examples to get any answers,

then this also turns out to be the best search that I could find at least,

which is interesting that you use this input order.

But surprisingly enough, this other search that we saw,

the search on potions was not nearly as bad as you think.

It's actually one of the most robust searches there are.

Yeah.

Okay.

Do we have any data file that is difficult

enough so that we will have to try restart as well?

Well, uh yes.

So, that's a good point and we can try restart by going into here and adding,

let's choose the simplest kind of restart.

Alright, so we won't change any of the default.

Exactly.

And we use Luby, right?

So Luby is very robust kind of restart because it just

tries lots of small restarts and a few big restarts.

Alright, let's see how that because we

take our optimal model and we run it now with Luby.

Now I just see what we ran,

okay, on this base.

There's new, with Alchemy 5, right?

It took, right so we were unlucky.

Right? For Alchemy 5, remember?

Yes.

Now we're running Alchemy four.

So, what happened? Yes, okay.

Why don't we start all over again.

Yeah, exactly. So Alchemy new.

This is four.

Yes. I want to run the five don't worry.

Okay. That's sort of what i want to do.

Okay. Alright. Okay, Alchemy 5 with restarts.

Yes. Alright? Point 013 seconds,

20 failures, three restarts and we got the optimal.

If we compare that.

Without restart.

Without restart, go back and run it again, right?

Remember this was our bad case.

Right.

Right?

Okay.

So this is the thing that restarts give you.

Here we were just unlucky.

It's a good search strategy,

but we just got stuck.

We found some bad decisions at the top and we couldn't undo them.

Alright? But turning on restart,

suddenly it's almost instant.

And only in three restarts.

Yes, exactly. We don't need that many.

We just made, we're just unlucky right at the top of the search strategy here,

making a decision that we couldn't get out of.

Whereas here, we restarted,

undid that decision and found a better solution.

And indeed if you take this combination,

it's a combination with restart which really makes this robust, alright?

Actually restart improves almost all the search strategies

that I played around with for this example.

Alright.

Just because it's very easy to get stuck in

the wrong place and then you can take

a long time to get out of it and restart will stop that.

So restart in general was you might slow you down slightly,

but it just makes search much, much more robust.

So we have just demonstrated how we can combine

all these advanced search strategies including a sequential search,

restart, as well as failure base search. How they can do wonder.

Exactly. So here we're using our most powerful variable selection heuristic.

But actually not, we're doing the search in a different direction than normal.

We're actually fixing the objective.

So we're trying to get the smallest possible value.

It means that actually you'll only ever get one solution right,

because the first solution you find will actually be the minimum,

because once you find a solution with objective 26,

you're not going to try one with objective 27.

Alright.

But in this case, for these examples, we can do it very well.

Right, it's not a good, if we get

really really big hard examples that we can't solve in time,

this is a terrible search, right?

Because it only either finds the optimal solution or finds nothing,

but turns out for these problems and even the bigger ones we can easily solve them.