1.3.6 Module 3 Summary

Loading...

來自 The University of Melbourne 的課程

Basic Modeling for Discrete Optimization

163 個評分

The University of Melbourne

Basic Modeling for Discrete Optimization

163 個評分

Optimization is a common form of decision making, and is ubiquitous in 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 in manpower and material resources management also allow corporations to improve 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, all of these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students interested in tackling all facets of optimization applications. You will learn an entirely new way to think about solving these challenging problems by stating the problem in a state-of-the-art high level modeling language, and letting library constraint solving software do the rest. This will allow you to unlock the power of industrial solving technologies, which have been perfected over decades by hundreds of PhD researchers. With access to this advanced technology, problems that are considered inconceivable to solve before will suddenly become easy. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s

從本節課中

Modeling with Functions

In this module, you will learn how to model pure assignment problems and partition problems, which are functions in disguise. These problems find applications in rostering and constrained clustering. In terms of modeling techniques, you will see the power of common subexpression elimination and intermediate variables, and encounter the global cardinality constraint for the first time. MiniZinc also provides constraints for removing value symmetries.

1.3.1 Modeling Functions9:12

1.3.2 Another Assignment Problem Example8:08

1.3.3 Modeling Partitions10:45

1.3.4 Global Cardinality Constraint9:45

1.3.5 Pure Partitioning14:36

1.3.6 Module 3 Summary5:30

與講師見面

Prof. Peter James Stuckey
Professor
Computing and Information Systems
Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering

Okay welcome to the summary of module three.

So what's happened in the story, Jimmy?

>> Well, a few things happened.

We've seen how Cao Cao and Liu Bei, they have successfully lead the coalition in

several strikes against Dong Zhuo's army.

And then also together with Yuan Shao, they have also claimed a new city as well.

At the same time,

a very important comeback happened between our three heros and Lu Bu.

It was a draw, but Lu Bu had to flee.

>> Right, yeah.

So technically, what are we seeing this week?

So this week is all about functions.

And we started off looking at the assignment problem,

which is about building an injective function.

So the assignment problem, we have one set of objects, the domain, and

another set of objects, the co-domain.

And we're basically trying to assign one of these co-domain objects to each of

the objective domain, and that's an injective function.

And it really actually is the basis of where the all different

constraint comes from because that's what is encoded.

>> But assignment problems are easy to solve.

>> Yes, so if you just have a pure assignment problem, then

actually there's very specific techniques, that's mostly matching techniques,

which will solve those problems very, very quickly.

The problem is, in the real world, nothing is likely to be a pure assignment problem.

And so there'll be side-constraints, and

then we'll need to use more general technologies

like the discrete optimization technology which we're talking about in this course.

>> So you mean a side constraint will essentially break the easiness of and

assignment problem.

>> Yes, absolutely, the summer prom can become arbitrarily difficult if we just

added just a few, what looks like simple side constraints.

>> We can also look at the general functions.

>> Yes, so we move on to general functions and

now we can think of those functions in two different ways.

So we can think as a mapping from the domain to the co-domain,

just as a normal sort of functional viewpoint.

>> Yeah. >> But

we can also think of them as a partitioning,

where we're basically taking the sets of the domain and

partitioning them by the value that they're given in the co-domains.

So it's really breaking up the domain into sets all labeled by one of the co-domains.

>> Okay, so this module is all about functions.

>> Yep. >> We've also learned

some modeling techniques as well, right?

One of them is common sub-expressions.

>> Yes, so common sub-expressions are very important if we have the same

thing that we're trying to use in multiple places in our model, and we should often

give it a name, give it an intermediate variable, and reuse that variable so

that we're telling our solver not to basically compute the same thing twice.

>> So comments of expressions are not good things so we should eliminate them.

>> Absolutely.

Now, many think we'll try to do this for you but it's much

better if you do it yourself, then you're guaranteed to know they're eliminated.

Sometimes minuting won't be able to determine that something is really

the same thing.

We also saw a new global constraint called global cardinality.

>> So global cardinality is great kind of extension of all different,

very much attached to the set partitioning viewer functions, which allows us to count

how many values in our domain are being assigned to each partition.

>> So we going to see more of global cardinality and

its relatives in chapters to come.

>> Absolutely, that’s an important global constraint.

>> We also saw symmetries, a special kind of symmetries called value symmetries.

>> Yes, so value symmetries are very common discreet optimisation problems

where two values are interchangeable.

We saw it in the clustering problem where the names of the two clusters really

didn't matter and in order to defeat these symmetries,

we introduced the value proceed chain global constraint.

Which is really designed exactly for

this, to get rid of asymmetries to only leave one possible answer.

>> Actually without the value proceed chain,

we could also consider adding some sort of ordering on the values as well, right?

That's one other way of breaking values asymmetries.

>> Well, value proceed chains effectively does that by ordering where those values

appear in our solution.

>> Okay.

>> So we've seen some applications actually some, we saw rostering,

that's a very important discrete optimization problem done by all small and

large corporations around the world everyday.

>> When we have constraints with our clustering problem,

we could make use of discrete optimization technology to solve such problems as well.

>> Yeah, so clustering by itself, if we're just doing pure clustering, then there's

thousands of clustering methods out there which will be much more efficient and

designed for very large problems.

But once we add side constraints,

again, a lot of these things are not applicable anymore, and then we need to

think about using more generic technology like discrete optimization technology.

>> Okay, when it comes to the workshop and

the assignment we have to introduce a very important person, Diao Chan,

who is actually going to break up the friendship of Lu Bu and Dong Zhuo.

>> Yeah, so the way she's going to do this is to seduce both of them.

So the way she seduces Dong Zhuo is by giving the great feast, so that's what

you're going to be working out, it's how she can prepare the best possible feast.

And the way she seduces Lu Bu is with a dance.

And you're going to have to work out the best dance she can make.

And these are complicated problems which have

interesting constraints about the sequence of what goes on.

In the workshop solution,

we'll actually introduce a new global constraint called regular.

You can do the workshop without it but when you look at the solution,

you'll be able to see that as well.

>> It's interesting to see how a feast and a dance can change history.

>> Absolutely.

>> Okay, we'll see you after the next module.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取