1.2.2 Choosing a Set Representation

Loading...

Из курса от партнера The University of Melbourne

Basic Modeling for Discrete Optimization

140 оценки

The University of Melbourne

Basic Modeling for Discrete Optimization

140 оценки

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 Sets

In this module, you will learn how to model problems involving set selection. In particular, you will see different ways of representing set variables when the variable has no constraints on its cardinality, has fixed cardinality and bounded cardinality. You also have to ensure all model decisions are valid decisions, and each valid decision corresponds to exactly one model decision.

1.2.1 Selecting a Set9:38

1.2.2 Choosing a Set Representation7:08

1.2.3 Choosing a Fixed Cardinality Set10:55

1.2.4 Sets with Bounded Cardinality13:06

1.2.5 Module 2 Summary3:33

Познакомьтесь с преподавателями

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

Although the Yellow Turban Army was defeated, the Han Nation was still in

a state of chaos under the cruel rule of Dong Zhuo, a powerful warlord

who controlled the young Emperor Xian with his unjust commands.

A coalition of other warlords, headed by Yuan Shao, declared war against Dong Zhuo,

in order to stop his lawlessness.

Liu Bei, Guan Yu and Zhang Fei were part of the coalition.

The collation army fought against Zhao Yun's army at a place called Yu Lui.

But failed many times to defeat Zhao Yun's army.

Cao Cao, a member in the collation was familiar with military science and

noticed the special formation of Zhao Yun's army.

Don's army used Bagua theory to establish their special formation.

They formed ten different formations or

wall each of which had different Bagua properties.

The ten walls were related in such a way that when a wall, for

example wall nine was attacked, other walls with the same Bagua properties,

walls two and ten with, the wind property, would become unbreakable, and

therefore, pointless to attack.

For the same reason, if wall five was attacked, then the other

five walls that shared the water and earth property would be unbreakable.

Now, aware of this strategy, Lui Bei turned to his magical tablet to

ask the best way to attack the gates and achieve maximum damage

[MUSIC]

Liu Bei has to attack Dong Zhuo.

Now, he's a master of tactics and he has a very complicated

formation which is protected by the magic of the Bagua.

So, Liu Bei has ten possible places he can chooses to attack this formation.

And these spots are protected by properties of the bagua.

Now, each of the spots is backed up by the different sets of properties of the bagua.

So we can see here the ten different positions that Liu Bei can

attack and which of them is protected by which property of the bagua.

But we can think about that another way.

So we can think about mapping for

each of the Bagua symbols which of the spots they defend.

So the magic power of the Bagua is such that if Liu Bei attacks one spot,

then all the other spots which are protected by the same

any symbol that protects that spot will be reinforced and

will not be able to be attacked.

So for example, if you attacked spot number 5 which is defended by these two

symbols of the Bagua, then spot 6, 8, 10, 1 and 3 which share a symbol.

So, 1 and 3 share this symbol and 6, 8,

and 10 share the other symbol, then he won't be able to attack those 2 spots.

So his problem then, is to decide which of the spots that he should attack.

And not all spots are equal in terms of how much damage he can do.

So some spots he can do a lot of damage, so spot one and spot ten for example, and

other spots, he can do and a little bit of damage.

So he has to pick a subset of the spots to attack, at most one spot for each symbol

because of course once he attacks one spot for that symbol, all the other spots for

that symbol would be magically defended, in order to maximize the damage.

So here's our set selection problem.

We're given a number of 1 to nSpots, each is associated with a symbol.

And we choose a subset of those spots, which includes at most 1 for

each of those subsets and maximize the damage points of the chosen set.

So for our data here, we've got 10 spots.

We've got a damage associated with each of those spots.

We've got eight symbols and here's an interesting thing.

And many think because it's using Unicode, we can use arbitrary characters here.

So these are quite legitimate characters in.

And each of these symbols has associated with it a set of spots.

And here we've used colors so

you can see the association between those symbols in which spots they defend.

So if we think about a greedy algorithm for this problem,

we can see here's the different spots numbered and

then we've connect them together by the symbols that protect them.

Now greedy algorithm to tackle this problem would say well choose

the spot with the largest damage available and attack that.

And then eliminate choices that are no longer valid and

then pick the next spot with the largest damage available and keep going.

So as it turns out,

the first place we can attack with the largest damage is spot number one.

But once we do that, we have to eliminate every other spot which shares a symbol.

So we have to eliminate, for example, spots four and six,

they share that symbol.

But we also have to learn all these other spots because they also share a symbol

with spot number one.

Which only leaves spots 9 and 10 left over and we look at the damage of spots 9 and

10.

Spot 10 is also a high damage spot, it requires 10 damage.

And then if we eliminate the remaining things we eliminate 9 and there's no

more spots and we can see that gives a solution of attacking at spots 1 and

10 with a total damage of 20.

Okay let's go back to the model.

So we have the number of spots and we're going to generate a set of ints which just

determines that set one dot to n spots telling us that range.

And with each of those spots we're going to associate a damage,

then we have our symbols at the Bagua.

And for each of those symbols we have the groups of spots,

the set of spots which associated with that symbol.

And then here's our decision.

Which sets of spots should we attack?

And then we have the constraints.

So really only one constraint we have is for every symbol,

then we can only attack one spot which is associated with that symbol.

So we look at the places we attack, the same spots we attack the intersection with

the group spots associates with the symbol has to be less or equal to one.

So that's the only constraint of the problem, and then,

what are we trying to do?

Well, we're trying to maximize the total damage.

And what is that?

Well we just sum up for all the places that we attack,

all the spots we attack, the damage.

So we're trying to maximize the total damage.

So it's a fairly straightforward model.

And if we run that model, then, we're going to get a solution,

a very different solution from greedy algorithm.

We're going to attack spots 4, 5, 7, and 9 for total damage of 21.

So, we've done better than greedy algorithm, slightly better but,

of course, anything is better for Liu Bei

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play