Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08
Workshop 10
Loading...
From the course by The University of Melbourne
Solving Algorithms for Discrete Optimization
4 ratings
From the lesson
Advanced Constraint Programming
In this module, you will see how Branch and Bound search can solve optimization problems and how search strategies become even more important in such situations. You will be exposed to advanced search strategies, including restart search and impact-based search. The module also uncovers the inner workings of such global constraints as alldifferent and cumulative.
Meet the Instructors
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
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.
Still times out.
We only got the same thing.
Nodes and failures. It's a bit hard.
When we time out, it's a bit hard to tell.
So you can see there failures 300,000 versus 50,000.
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.
So in six seconds, we can traverse less nodes because we've got a much bigger model.
Yeah.
Alright. Let's see if we can actually finish one of these off.
Okay. I got it. That would be better. Alright.
So Alchemy two, with this search base,
we can actually prove optimality.
So there was a best thing with all of the constraints.
Let's run it with with only the primal model.
So now, we can compare. So what do we see?
I think 0.35 was the time.
Is it 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.
We're not getting any more solving.
If I run this one I can prove also was that the same one.
Yeah.
I think I didn't select it. That's it.
Ideally, what I want to do is find one which I can actually prove optimal in 30 seconds.
Using that one, I probably won't.
Using this one either, it may be.
No.
No, but 33, in fact,
I get a lesser objective. I got further.
Yeah.
So obviously, the primal only is better than our base in this example.
But why don't we look through the base?
In fact, this time,
why don't we save it as a new one?
So we can look through and remove bits that we don't need.
Alright. So what we want to do is look at
every constraint and think about which is the right way to specify it.
Right.
Okay. So what about the potion prequisites,
which do you think is the best way of specifying this constraint?
I mean from my gut feeling,
I would select the one that is the simplest.
Exactly. Okay. And that's very clearly the first one.
Yeah.
Right. So let's comment out those ones.
You could just highlight all the lines that you want coming out.
Yes. I would just make more mistakes if I try to be a power user.
Jimmy is a power user. Alright.
Number of potions made on each day,
which we think is the most simple.
Well, I think the last one is just looking up the cardinality.
So that looks to be the most simple,
so let's keep that one.
Okay.
Alright. The calculation the outcome is working on one day.
We can see these two look almost the same,
but this one, we've got I have been able to use a global.
So hopefully, the global is going to help us.
So let's look at that.
Okay. So these are redundant.
No, these we don't need because we're keeping the day view
then although we might want to
keep that's a global as well, it might be helping us. We don't know.
And now, we're only in the end if you think about it.
We're only ever used to day and the potions
views and we've never used the potion day view.
So we don't need that channeling.
We don't need this channeling. We just need this channeling.
Yeah.
Okay. We'll keep all the redundant constraints.
Now for other linear constraints, as we were talking about earlier,
since this actually makes use of the day variables cleverly,
it's likely to be better.
Again, it's simpler than these other versions.
Okay. Now we hope that we've improved our model.
Okay, now again, it's hard to tell with these search strategies.
This is, the problem that we're stuck with
a fixed search strategy which isn't very good, right?
Right.
And that's the only thing we can really compare.
So what about we try a different search strategy.
Okay, so.
You have prepared five.
I have prepared a number.
So lets try search two.
So here, there we were just doing the day in order.
Now let's take day with a first failure.
So we 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,
like I remember we didn't, in six seconds,
we didn't get, we got to an answer 32.
Now in point 025 we got to an answer of 30.
That makes a big difference.
It seems a lot better, okay?
So that, currently Alchemy is our primal only.
Let's load 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, was the first fail.
Oops, alright.
So if you ran our original model,
okay, we could solve it,104.
Failure is eighty seven. Let's have a look at 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 gonna find the search strategy.
Change that to first fail.
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.
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
