Set Cover

Loading...

Del curso dictado por The University of Melbourne

Discrete Optimization

254 calificaciones

The University of Melbourne

Discrete Optimization

254 calificaciones

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

De la lección

Constraint Programming

Constraint programming is an optimization technique that emerged from the field of artificial intelligence. It is characterized by two key ideas: To express the optimization problem at a high level to reveal its structure and to use constraints to reduce the search space by removing, from the variable domains, values that cannot appear in solutions. These lectures cover constraint programming in detail, describing the language of constraint programming, its underlying computational paradigm and how it can be applied in practice.

Conoce a los instructores

Professor Pascal Van Hentenryck
Dr. Carleton Coffrin
Adjunct Lecturer
Computing and Information Systems

Okay guys, so this is the set covering assignment which is not really assignment

and so this is a novelty in this session.

And the key idea here what were trying to do is to have an assignment that kind of

a thick assignment which people can submit their solutions and can share quote okay?

So you can share code you can share ideas but not code on the other assignment.

But here what we want to do is to make sure that you guys can actually share code

and show code on a particular assignment so

that people can say this is really how you do local set,

this how can you do it contrary programming software and so on, okay?

Sometimes it's like in programming.

Looking at the code of somebody else can actually help you

thinking about how you can actually implement something yourself and

this is what we are trying to achieve here, okay?

So I'm going to describe the set covering assignment and then I'm going to

talk about some of the ways you can share that later on in this video, okay?

Now set covering itself is a very interesting problem that pops up

everywhere, okay?

I'm going to use one real life example here, but there are many,

many other examples.

And this actually is a problem that pops up in a lot of other actually

real applications.

Either it's on its own,

but generally as a sub path of a more complex algorithm, okay?

So this is an example using a fire station that has to cover a region.

So what you see here is a big geographic region, okay?

And everyone of the big dot there, the black dot,

is a location where you can set up a fire station.

And the key idea is that you have to cover all the small region there.

They are numbered like zero, one, and so on and so forth.

You have to cover 80% of these things in seven minutes, okay?

And so once you get, that's requirement for emergency services.

And so what you want to do is select a subset of them so

that you basically cover the entire region at the minimum cost, okay?

This is a for instance [INAUDIBLE] solution, okay?

So you see here,

this particular fire station is covering this part of the entire global region and

these subregions over there, okay, and so on and so forth, okay?

And so in this particular case, you have six selected fire station

that basically satisfy the legal requirements of the entire region, okay?

And you try to do that of course at the minimum cost, okay?

Satisfying the legal requirement, getting to the people in the time that is

specified by law but also the minimum cost.

So this is how we can model this thing more formally, okay?

So in a sense, all the regions that you have seen in the particularly

in the example that I have shown are going to be called item, okay?

So we are basically given a number of n items, and

we will have to cover these items, okay?

How do cover them?

We cover them by Set, that's why this is called Set Cover, okay?

So in this particular case to set a fire station, okay?

And it's essentially a fire station is defined, or

a set in the more abstract version, is defined by two things.

It's cost, that's the cost it takes you to actually build it, okay?

And then the items that it cover.

You know, when you have a fire station you will know which of the regions

you will cover in seven minutes.

80% of which you can cover in seven minutes, okay?

And so when we look at the abstract version of the problem, for

every one of these sets, we know which item they cover.

We get this SI, the set SI which tells you that

set i is actually covering that many items.

Okay.

And then so this is the data, these four things there I'm listing out is the data.

And then the only decision variable that you need in this particular problem is

find out if you select set i or not, okay?

So Xi one if you select set I think fire station.

I am selecting fire station i.

And zero otherwise you don't select fire station i, okay?

And so now once you have this decision variable in this data you can

formulate the problem mathematically, okay?

And what you see there is what you want to do is minimize a linear sum again.

And this is the sum of the cost of opening everyone of the fire station.

So this is ci which is the cost of set i times xi which is zero if you don't open,

if you don't select that set or one if you don't select that set okay?

So you basically have the cost of all the sets that you are selected or

all the fire stations that you are building if you want, okay?

And then you have two constraints, the first one, actually one constraints,

the one constraint that you have is that every one of the item has to be selected.

How do you do that?

Well, the sets they belong to, okay?

You have to make sure that for

every one the item there is at least one set that it belongs to which is selected.

So you basically make sure that the sum of of the variable xi

that cover that particular item is greater or equal to one.

An item can be, they can be covered by two different sets and that's fine, but it has

to be covered by at least one and that's what this constraints is expressing.

And of course you build the entire fire station on that so

this is a binary zero one variable, okay?

So that's basically the formulation there.

The input is a little bit more interesting.

The only thing that you would have is a essentially the number of items that

you need to cover and then the number of sets that can be used for covering them.

And the rest of the data of the instants are really related to the sets, okay?

They're going to specify the cost of every one of the set, and then for every one of

these set you will have a list of all the items that they cover, okay?

So essentially every one of these lines here may have different number of

elements because they represent for

every set what are the items that are covered by that set, okay?

So in a sense to summarize you have the number of items you have the number

of set, you have one line per set, you have the cost of the set, and

then the list of the items that are covered by that set, okay?

The output is very simple, once again, objective function,

whether it's subtimal or not and then which of these sets have been selected.

That's the decision variable, that's the values that we want to see, okay?

So it's a zero one variable for every one of these sets, okay?

This is an example of an instance, you see the number of items,

you see the number of sets, five and four, okay.

So you obviously have four lines since you have four items, okay?

The first one is telling you that this is the cost of 12, and

then that particular set is covering item zero and item two, okay?

And so you can see that item zero is only covered by that set, so we know for

sure that that particular set will have to be selected, okay?

This is an example of a solution okay?

So it's a cost of 24, it's not optimal, it's not prove optimal, okay?

So what you see there is that we select set 0, set 1,

we don't select set 2, but we select set 3, okay?

So that's essentially the output,

very simple output which sets are you selecting, okay?

So as I said, the key point about this assignment, it's not a real assignment,

it's something which is open source, you can share your code, okay?

So we give you some code, some simple greedy solver, some constraint programming

software, you can look at that code, and you can get inspired by it, okay?

It also shows you how you can code an external tool, okay?

So go and look at this, okay?

So this will give you a sense of how these kinds of software are organized.

And it can give you some inspiration when you actually build your own, okay?

So you start from something and

you can actually see how it works on this particular example, okay?

Now you can design your own code and then share it with some of your friends, okay?

So you can use GitHub for this optimization and

share your code with your colleagues.

If you get a better local search,

a better constraint for running shoulder, a better mathematical for

running, a model accurate for solving this problem, just share it, okay?

You can do this and your colleagues you classmates can actually look at this and

get inspired by it, okay?

So once again, the goal here is to share information so that people can get

started, people who don't have experience in optimization can look at some code and

know how to actually build some more complex solvers, okay?

Don't list results we don't care about the results here,

this is really about sharing the code, okay?

So having a look up table is the most boring algorithm ever.

So have fun this is an assignment that you can share with other people where you can

discuss the various techniques, where you can go into the detail of the code.

So this is something that was recommended to us last year and

I think it can make a difference for people who are really starting in discreet

optimization and want to look at various code before they start their own, okay?

Have fun guys, this is a very simple assignment, no pressure at all.

So you can see code, you can share code, so

this is an interesting novelty in this particular session, okay?

Have fun guys, see you.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play