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 9
Loading...
From the course by The University of Melbourne
Solving Algorithms for Discrete Optimization
2 оценки
From the lesson
Basic Constraint Programming
This module starts by using an example to illustrate the basic machinery of Constraint Programming solvers, namely constraint propagation and search. While domains represent possibilities for variables, constraints are actively used to reason about domains and can be encoded as domain propagators and bounds propagators. You will learn how a propagation engine handles a set of propagators and coordinates the propagation of constraint information via variable domains. You will also learn basic search, variable and value choices, and how propagation and search can be combined in a seamless and efficient manner. Last but not least, this module describes how to program search in MiniZinc.
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 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.
And let's try the end time variables.
All right, so you see same number of failures in this case.
We basically have, if we try, switch between them,
basically we're going to get- >> It's the same in this case.
>> Basically almost the same.
Yeah, same time, almost everything the same.
Actually, exactly the same. >> [LAUGH]
>> [LAUGH]
>> Interesting.
>> We would try large examples.
>> Yes we should probably try a large
example. You can't
learn everything from just looking at one example, that's for sure.
So lets look at the second example, so here we've done start time.
7 phase, I went straight to the optimal.
Let's try end time, whoops,
come back, yeah. >> Exactly the same,
again. >> Well,
it's because we're doing import order. >> Right, right.
>> [LAUGH] When you're doing import order,
the start time and
the end time are basically the same thing. >> Yep.
>> So that's not surprising at all.
So let's try something a bit cleverer, let's-
>> I mean, how would a human being do when
he or she is trying to schedule such task? >> Yeah.
>> We should,
perhaps we could try smallest because we would like to select the variable with
the smallest remaining value in the domain of
the variable. >> Alright so if we do that, if we do
the start time, we pick the smallest start time, we set it to its minimum value.
This is a very standard scheduling example where we just try to make things happen as
early as possible, starting from the beginning of time, right?
So we find the solution in six phase,
of course we are doing very small examples here.
And if we do the end time now we should get a difference,
right? >> Right.
>> Because the smallest end time is not
necessarily the same as the smallest start time.
Right, so we do see a difference, right, 32 failures versus 15.
Yep, let's go to a slightly bigger example.
Alright, so here's example three, that's using end time for any 5 failures there.
So it did very well, maybe let's have a look what happens when we do start time.
So 6 failures, so there you can see actually if you look at the time,
the end time was better. >> Right.
>> Right, so of course,
end time is finally what we're trying to optimise.
So in that sense, it's not a bad idea to minimise on end time,
as well.
>> Right. >> Alright.
>> We have not tried the B variables.
>> Okay, alright.
Well, we should definitely try the B variables.
>> All right, because it's a-
>> Okay, it's a two dimensional array, so
let's just make it one dimensional, fill in the int_search.
And now, smallest doesn't really make sense for boolean variables, right?
The smallest value will be 0 for all these boolean variables.
So that's just 0, unless if they're fixed, they're either going to be fixed to 0 or
fixed to 1, in which case we're not going to do anything.
>> First fail doesn't make sense either.
>> First fail doesn't make sense either,
so basically input order is about all we can do.
Now we'll see in the next week, some more interesting
variable selection policies, which will be able to differentiate between booleans.
Alright, but let's run this one with booleans.
Alright, nine failures, so how did that compare?
Not as good as the end time one, which is six failures, or
the five failures. >> Right.
>> Yeah, let's have a look at another
example.
Alright, so there we're now on example four.
We had 4 failures, now actually I need- >> Yeah.
>> I want to keep track,
so basically that'll be the insert one.
Let's build our other.
So our current best search strategy is smallest, alright?
And then indomain_min, complete, so
we're going to basically compare these two.
So if you compare that one you can see,
wow. >> Wow.
[LAUGH] >> So did that time out?
>> Yeah, yeah.
Timeout, operating system error. >> [LAUGH]
>> [LAUGH] And you can see,
okay it's found a solution at 31.
What happened when we used our booleans?
Oh it found a solution
of 31, in 0.7 seconds.
>> Wow, it's- >> Right?
So this one actually found the best solution, but it couldn't prove it, and
it spent a lot of time,
a lot of failures trying to prove optimality, but wasn't able to, right?
Let's have a look at a different example.
Alright, example five,
off we're going to go. >> Time out again.
>> Time out again, okay, and
we didn't prove optimality, there's no double line there.
But if we can flip back to the boolean search that we're doing.
What happens? >> Wow.
>> Proved optimality.
>> Yeah.
>> Okay.
>> Within a second.
>> Yes, within a second.
So we're interestingly seeing,
even though this boolean set really knows nothing, right.
Because basically we're just picking input order and setting them to false, so
we know nothing about what's going on,
we're using no clever dynamic things about what's happening
in the solver. >> And it's not according to any of
the scheduling knowledge- >> No.
>> That we have.
>> Exactly, it's still winning, okay?
Now, let's try one of the bigger examples.
Okay, so let's try number 11.
Okay so you can see we find plenty of solutions for number 11.
We're going to hit time out presumably,
it's stuck at 10:48, and we've lost our statistics.
Let's try the other one.
Okay so our best, so that was on the boolean, so
we've got a makespan of 10.48 now, six seconds.
What if we run our scheduling example?
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.
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
