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
1.2.3 Choosing a Fixed Cardinality Set
Loading...
From the course by The University of Melbourne
Basic Modeling for Discrete Optimization
128 оценки
From the lesson
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.
Meet the Instructors
Prof. Peter James StuckeyProfessor
Computing and Information Systems
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Liu Bei recommended the strategy obtained from the tablet to the leader, Yuan Shao.
But Cao Cao warned that there are only three elite groups within the army
to attack the walls.
And so a new strategy of attacking three walls was needed.
Once again, Liu Bei turned to the magical tablet to find a suitable strategy.
[SOUND] >> So the problem with the last model for
attacking the bi-wall was was Liu Bei didn't have enough soldiers.
So we've got to revise the question we're actually going to answer.
So we've got a set of spots, and h is associated with the set of symbols.
And we have to select a set of spots of a given size, so
now we have three squads to attack.
And we want to maximize the damage points we can do for
this chosen set of a particular size.
So now we're adding something to our data file.
We're adding the size of the set that we want to choose.
So we could easily add just one extra thing to our model to do this, right?
All we have to do is say, well, we have this attack set that we're choosing,
we're just going to force the cardinality of this set is equal to size.
And then that's going to force what we choose exactly three attack positions, and
we execute our model, we're going to get a new solution.
The damage is less than before, but that's okay, we've solved the problem.
But once we've got this new constraint, the size of the set we're choosing
is known, we can actually model the set differently.
And let's think about why we might want to do that, so
rather than having a variable set of spots attack with this cardinality saying,
the cardinality equals size, we can instead model it this way.
We're going to have an array of one to size elements of var SPOT.
We are going to say that the attacks are just the elements that occur in
this array.
So why should we do this?
Well, imagine that the number of spots is 1,000, and we need to pick 4.
So in the first representation,
we've basically got a set variable with 1,000 possibilities in it,
which in many solvers, will map down to 1,000 Boolean variables.
So we basically have to make 1,000 true, false decisions.
Is this value, this spot in or not, 1,000 choices have to be made.
In the second representation, in this array representation, we have four
integer variables, which are the four spots that we're actually going to take.
But there will be some issues that come with that.
So let's think about a smaller example.
So here we have an array from 1 to 3 of variables from 1 to 10 that we want to
represent.
For example, the choice of a subset of the values 1 to 10 of size 3.
Well, how many values are there of this array?
Well, there's 1,000 possible values of that array.
But here we have the actual thing that we're trying to do,
which is we're trying to pick a subset of the value of the numbers 1 to 10,
which is of cardinality 3.
And if we think about how many possible values there on that, well, there's,
in fact, 120 possible values.
There are 120 different subsets of the numbers 1 to 10 of size 3.
So obviously, there are lots more arrays than there are subsets of size 3.
So the problem is that some of these array solutions
don't represent subsets of cardinality 3.
So if you think about if we chose that the values of the variables in the x
array were 1,1,1, it wouldn't represent a set of cardinality 3.
It would represent the set 1, which is not a set of cardinality 3.
If we chose the values 1,2,1 in our array, it would represent the set 1,2,
which would not be a set of cardinality 3.
So that's one of the reasons that there are thousands more values
here in the array than there are in the sets.
So the first thing we need to do is ensure that all the values in this array
are different, otherwise it won't represent a set of cardinality 3.
So we can add some constraints on our array saying that all the values in
the array elements are different, okay?
So that we can do that straightforwardly, and that will get rid of that.
So if we now think about our array with these extra constraints that all
the values are different, we see how many possible values are.
Well, there's 10 x 9 x 8 = 720.
We still have more values left over with the array than
there are sets of cardinality 3.
So what's going on?
Well, there's still some multiple representations of the same set.
We think about the set {1,6,10} then there, all these array values correspond
to the same set {1,6,10} obviously in the same order but also {10,1,6},
{10,6,1}, {1,10,6}, {6,10,1}, and {6,1,10}.
Every order of the values in the array ends up representing the same set.
And so what we have to do to get rid of this is make sure that we only allow one
of these orders to appear in the array values to make sure there's only
exactly one representation of the set.
And the way to do this is to ensure that the values in the array are ordered.
So here we can just make sure that the values in the array are increasing,
in which case, there'll be exactly one way to write down this set.
In this case, {1,6,10} will be the only way left over.
And if we do that,
we can see that this constraints here forcing them to be ordered will in fact,
also force that they're not equal, and so we can get rid of these constraints here.
They won't be needed anymore once we force them to be ordered,
that would certainly be not equal.
So once we do that, we'll have got down to exactly the same number of possibilities.
So this brings up a critical issue in modeling decisions.
So when we're modeling decisions in our problem,
they are not necessarily the decisions we have to make in our model.
Because decisions we make in a model have to be representable
in the modeling language that we're using.
So if it's possible, we make them identical.
But sometimes we're making decisions in our problem which are complicated like
a path in a graph or a tree structure, things that
just can't be expressed directly in the modeling language we're using.
So a critical modeling issue is making decisions in our model, which satisfy
constraints and ensuring that they are valid decisions in the problem.
So we add constraints to our model to make sure that the only
answers that come out of the model are valid decisions to the problem.
So we add these constraints in, just have we seen here, if we add constraints,
forcing our array once we're not equal.
To make sure that the array decisions in our model end up being
valid decisions for our problem.
And another issue that comes up is that multiple decisions in the model can
reflect the same decision in the problem.
So an example here is where we had x could be [1,2,7] or
[7,2,1], they both represented the set x [1,2,7].
So another critical issue from modeling is to try to have only one set of decisions
in the model corresponding to each solution in the problem.
So reflecting the valid decisions in the problem having only one possible way
of having that set of decisions in the model.
And we add constraints to remove all but one set.
So adding constraints in this case to force the array elements to be in order
did this.
So this in general is a notion of symmetry, and we'll come back and
talk about that in much more detail.
So these are two critical modeling issues we're seeing here for the first time,
but we'll come back to them many times throughout this course.
So let's come back to our problem,
we have our problem of solving the bi-wall with a fixed cardinality set.
Now let's use our new alternate way of building the model.
So our decisions now is an array from 1 to size of var SPOT.
So here is an array representation of the set of spots that we're going to attack.
And we're going to force it is a valid representation by forcing
that these attack positions increase in order so
that we know that we exactly get one copy of each spot.
We don't have duplicates, and they're in order, so
there's only one representation of every possible set.
And then we have to write our constraints using this new representation.
For these particular constraints, it's straightforward, we're going to sum up.
We have to make sure the cardinality constraint holds,
that we only attack every symbol at most once.
So this is easy enough.
We sum up for all the attacks in the array, the intersection with the group,
and that has to be less than or equal to 1 for each symbol s, so
that's straightforward.
And in fact, the total damage is even easier,
basically because we can just add up the damage for these spot attacks of i for
each of the i in 1 to size in the array, and that gives us the total damage.
So that gives us our fixed cardinality version of the model.
And we execute the model, and we've got our solution, just as we did with
the other simplified version, where we just added a cardinality constraint.
But for different kinds of datasets, with large sets of spots,
we would expect that this cardinality model could be much, much more efficient.
So in summary, we've got multiple ways of representing these fixed cardinality sets,
so we can have our var set of OBJ with the cardinality constraints.
And this is going to be good if the solver natively supports sets and
when this object set is not too big, or we have arrays from 1 to u of var OBJ,
which is very good when u is small.
If we're picking a very small set of objects out of a large set,
then this is typically going to be much more effective.
And we brought up two critical issues in modeling decision, and that is
we need to ensure that each solution to the model is a solution of the problem.
So we make sure that we don't leave other solutions possible in the model,
which don't refer to anything in the problem.
And we try to ensure that each solution of the problem,
only has one solution in the model and not many, many.
Sometimes we won't be able to manage this, but if we can, it's a good thing to add
constraints to our model to try to ensure that we do this.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
