>> So he's going to hire a bunch of alchemists.

Every day 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.

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

so he can only put a maximum number of alchemists into the workplace.

Okay, now so, of course, Shannon we'll like to save some money, so

he would like to minimize on the maximum number of alchemist that he would

need on every day across all the data in his preparation process.

>> Right, basically because he has to hire the alchemists for the entire period.

>> Yes. >> So he's playing for the maximum.

>> Yep.

>> All right, 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,

all right?

So here is our reading in of the data.

>> Right. >> Right, so

we're reading in the number of potions.

How many alchemists each of them need?

A minimum and a maximum number of potions we have to make on each day.

A number of maximum alchemists we have to use in each day, and

a prerequisite between the potions, right?

Here is a two-dimensional array.

Then we need the potion prerequisites.

>> Mm-hm.

>> Now that's pretty easy with the day variables, 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.

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 calculated in the day when the second was done, and

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

We can also do it with the SET variables, it's a bit trickier, all right.

So we're basically saying okay, if we look at all the days and

we have that this portion is done on day d1, right.

Then if we look at all the days before d1,

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

>> Wow, in this way of expressing the constraint, we are using if then.

>> Yep. >> And we are also using negation.

>> Well yeah, a negation of a boolean isn't too bad.

>> Okay. >> Okay.

>> Yeah.

>> 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 is a constraint.

>> Right.

>> Right, they're all there at the moment.

>> Yeah.

>> 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 in each day.

>> Yeah. >> Right,

so we can do this by just summing up for every potion,

right, if it's made in that day.

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

Very similar if I've got the booleans.

I'm just summing up the 01s of which potions are on that day.

>> Yep.

>> But if I have the potions, right, which actually gives me the set.

I just need to get the cardinality, right.

So it's simpler, this is simple in the SetView.

All right, what about the calculation of how many alchemists are working each day,

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

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

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

And that gives us the total working on that day.

So I'm summing across all potions.

Very, very similar in the boolean view, right?

>> It's just that this expression here day(p)=d is exactly equivalent

to this potion, potion_day[p,d].

And for the SetView, we can actually make use of a global constraint,

which is isn't normally visible, but it 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 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 flat sync.

>> It's a predicate.

>> Exactly, the solver g-code 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 we can also see that some

of the constraints are easier to express in a particular viewpoint.

>> Exactly.

>> Right.

>> All right, so then we've got some more constraints.

So potions are not assigned to two days.

Okay, so that's obvious in the day view, right?

>> Right. >> Because the day view,

I look at the potion, it's given a day.

It can't be given two days.

>> Exactly.

>> So that always happens.

Not obvious for the other ones.

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 SetView, I basically need that the sets for each day,

they all have to be disjoined.

So that's the global distraint, all disjoined.

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

>> Exactly. >> Yeah.

>> Basically two sets have to be disjoined >> All right,

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

>> Yeah.

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

We can channel between day and potion day.

>> Yeah.

>> And this is basically exactly the statement we said.

Potion day pd is exactly the same statement as saying the day that I made

potion p was d.

>> Yeah.

>> Right, we can channel between potion day and the potion view,

which is almost the same, right?

If I made potion p on day d,

then it was p is in the potions that are made on day d, right?

And for this SetView and the 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 mobile.

Right, so we have it.

So, just no, nothing wrong with not having global constraint here because in fact,

there's not much you can do better than these definitions, right?

>> Sure. >> Okay, we're also,

in order to make our model strong, we're going to add some redundant constraints.

So here it's 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 an alchemy of all the portions.

And basically if we add up all the numbers we have to get to the number of

portions, right?

So that's basically just redundant constraints.

Here's a tricky one and this is looking for everyday, we're sort of

looking at the number of portions that are made after this day, right?

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 the minimum number of algorithms we can use every day, all right?

And it has to be less than or equal to the number of days

left times the maximum amount we can use, which is the objective, right?

So it's basically your redundant media constraint, but

let's just look forward to say, well,

if all of these portions 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, right?

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.

>> Right? >> Yeah, so we don't need this constraint.

Any of these constraints marked redundant we can remove.

>> Right. >> And that's part of this workshop.

You'll have to remove all things which are marked redundant.

>> All right. >> Okay, we've got this, the day view.

Then we can do the same thing with the portion day view and

with the portion view.

Although notice they're not so clever, here, we're actually making use of

the fact that we can write down something directly, right?

That the day of this portion is after some day right, and

that's just a very single simple boolean.

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

We can get a solution in 17 failures.

All right, so now, our current lead, by the way, our searching we're doing,

is we're just using the data variables, we're going in order, and

we're saving over the minimum values.

Kind of like, very just naive.

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

It can't be changed by the constraints, right?

Basically we're always just taking the next variable,

saving to its minimum value.

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

>> Okay, let's talk about model again.

>> Exactly. >> So, right now,

we have a combined model, combining constraints and

variables from three different viewpoints.

And then they are channeled together.

Okay, so they work.

>> Yep, result.

>> So in essence each of the viewpoints, the variables and

the constraints, they are redundant with respect to the other viewpoint, right?

So we could actually comment out one of the viewpoints and

see how things will be like.

>> Yeah, yeah, actually,

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

So that's the primal view, the most obvious way we're writing it.

>> So we are only commenting out the constraints, right?

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.

Nodes and phase, it's a bit hard when we time out, it's a bit hard to tell.

>> Right.

>> Okay, so you can see there phase 300,000 versus 50,000.

>> Right. >> Okay, so that might be that we've got

a small search base, or it might be because we're

actually just doing less nodes per time, right?

So in six seconds,

we can traverse less nodes because we've got a much bigger model.

All right, let's see if we can actually finish one of these off.

Okay, that would be better.

Right, so alchemy two with this search space, we can actually prove optimality.

So there was our basting with all of the constraints in.

Let's run it with only the primal model, okay?

So now we can compare.

So what do we see?

I think 0.035 was the time,

this was 0.147, so definitely the other one took longer.

What about failures?

325 for the primal version.

>> Looks like the same.

>> 325, so in this case, we're basically driving straight to the same problem,

and we're not getting any more solving.

If I run this one, I can approve also.

Or is that the same one?

I think I didn't select it, that's it.

You have prepared five.

>> I have prepared a number.

So let's try search two, so here we're just doing the day in order, and

now let's take day with the first fail.

So we'll take the one with the least possibilities and set that up.

So that's generally a good idea right?

>> Yeah. >> So if we run alchemy 3 well.

>> Wow.

>> Remember we didn't in 6 seconds, we got to an answer of 32.

Now in 0.025 we come to an answer of 30.

>> That makes a big difference.

>> This seems a lot better, okay?

So that currently alchemy is our primal only.

Let's add in our base as well, which was everything.

That was the original model with everything in it.

And change its search strategy to be the same, so I can see,

this is use first fail, all right,

so if you run our original model, we can solve it, 104,

failures is 87, let's see how that compares with back here.

With the primal only, okay?

>> Same thing.

>> So, same thing.

So, in fact, by removing all those constraints,

we didn't change the search base.

What about our new one, which is, we hope, is the best one.

I'm going to find the search strategy, change that to first fail.

Yes, okay, let me run alchemy.

>> Why don't we start all over again?

>> Yeah, exactly.

So alchemy new.

I want to do- >> This is 4.

>> Yep, I want to run 5 don't I?

>> Yeah. [LAUGH]

>> Okay, that's what I ought to do.

Okay, all right [LAUGH].

>> Okay.

>> Okay, alchemy-5 with restarts, 0.013 seconds,

20 failures, 3 restarts, and we got the optimal.

If we compare that, if I go and- >> 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, right?

>> Yeah. >> Here we were just unlucky,

it's a good search regime, but we just got stuck,

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

Right by turning on restart suddenly it's almost instant.

>> And only in three restarts.

>> Yes exactly, we don't need that many.

We were just unlucky right at the top of the search tree here making a decision

that we couldn't get out of.

Whereas here we've restarted, undid that decision, and found a better solution.

And indeed if you take this combination,

it's the combination with restart which really makes this robust.

>> Mm-hm.

>> Right?

But actually restart improves almost all of the search strategies

that I played around with for this example.

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, it may 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 sequential search, restart, as well as failure based search.

>> Exactly. >> How they

can do on the- >> Exactly.

So here, we're using kind of our most powerful variable selection heuristic.

We're 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 then 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.

>> Right.

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