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.