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 who have completed Basic Modelling for Discrete Optimization. In this course you will learn much more about solving challenging discrete optimization 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 course will focus on debugging and improving models, encapsulating parts of models in predicates, and tackling advanced scheduling and packing problems. As you master this advanced technology, you will be able to tackle problems that were inconceivable to solve previously. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s
2.4.2 Rectilinear Packing without Rotation
Loading...
來自 The University of Melbourne 的課程
Advanced Modeling for Discrete Optimization
46 個評分
從本節課中
Packing
In this module, you will learn the important application of packing, from the packing of squares to rectilinear shapes with and without rotation. Again, you will see how to model some of the complex constraints that arise in these applications.
與講師見面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
Inspired by the benefit of packing the house ships together,
the general started to pack their battleships.
Battleships of armies from the same stage were packed into blocks, and
they formed four ship blocks, from four areas.
The Northern provinces, Yuan Province, Jing Provinces, and Xu Province.
Cao Cao asked Pang Tong to pack the four ship blocks and
the half ship block together to form a large block.
To pass through a river on their way,
the width of the large block could not exceed the width of the river.
To maintain stability, the length of the block needed to be as short as possible.
Again, Pang Tong came back to Zhuge Liang for help, and he pulled out the tablet.
[MUSIC]
>> So Cao Cao is very impressed with Pang Tong for this packing solution for
the houses.
And he has a similar worry that these battleships hold his soldiers, and
they too are getting nauseous, so he'd like to tie them up together.
Now, in fact, the soldiers come from various different parts of China, and
so they've tied themselves up already in their ship blocks.
And so these ships for all the northern provinces have already been tied up like
this, but we're going to model this just by this simpler
version where we're not going to look inside the individual ships, but
just break this up into a number of rectangles which give us the same shape.
And similarly, the Yan Province ships have been tied up like this.
And we're going to model this as just these three rectangles that
give us the shape of the Yan ships all tied together.
And Jing Province has tied their ships up like this,
which we're going to model by these four rectangles.
And the house ship block is being packed by Pang Tong,
very effectively, and it's tied up like that.
And finally, the Xu Province block is tied up like this,
they've done a very good job of packing their ships into a very tight rectangle,
which is going to be represented by these two rectangles.
So the ships all have to be tied up in a river of fixed width.
And so one thing we could do is just tie them up like this.
So we've tied them all together in this order, and they fit within the width.
But Cao Cao says, well, look, there's plenty of space here,
surely we can get a better way of tying up these ships so that they're more compact.
What we want to do is minimize the width so
that everyone's close together, and then it'll be the most stable possible.
So what we have here is the ship block packing problem, which is,
given this sequence of rectilinear shapes, so that is, rectangle shapes,
we're going to pack them together so that the resulting height does not exceed h, so
that's the river height, and we're trying to minimize the length along the river.
So our shapes are all rectilinear.
We know that our house ships are square in shape, the battle ships are rectangular or
rectilinear.
But in fact, we're not going to worry about that, because we're only going to
think about the individual ship blocks which have already been tied together.
So the ship blocks can look like this,
complex shapes made up of multiple rectangles.
So here's actually a more complex shape than any of the ship blocks
we're actually going to use.
But you can see how I can take any kind of rectilinear shape, and
I can break it down into individual rectangular parts, and so
I end up having, basically, a rectangle packing problem.
So how are we going to represent a whole lot of rectangles as one
ship block, these block shapes?
The way we're going to do that is to think about rectangles as offsets.
So we have the lower left corner,
that's going to say where we say the position of this shape is.
And then we need to know for each rectangle in this shape,
what does that mean about it.
So it's going to have an x offset and y offset, so here it's 0,0,
because it's the same.
And then an x size, so width 3, and height 4.
All right.
And so similarly, other shapes are here.
We have nothing actually in this lower left corner.
That's the base position of the shape.
But this rectangle here is at offset 0 in the x direction and 1 in the y direction.
It has a width of 4 and a height of 2.
And if you think about it, actually, if we rotate these shapes,
the offsets will change.
And we'll come back to that in the next lecture.
So, how are we going to represent this in a model?
Well, we're going to number all these different rectangle offsets.
And then we can think of a block In a specific orientation and
a set of rectangles with offsets.
And we can also share these rectangle offsets, if possible.
So we don't necessarily have just use one set of offsets, or one shape.
So here's our list of offsets, right,
these four numbers that make up a rectangle offset plus its size.
And then we can represent this shape by saying, well,
it's this offset plus this one, plus this one, all right.
So there's that guy, plus that guy is 3, and that guy is 4.
And so our representation here is the set of rectangle offsets 1,3,4.
And simply, we look at this shape.
So it's, again, made up of three rectangle offsets.
So this is one is number 2, this one is number 5,
and this one here is number 6.
And so its representation is 2, 5, 6.
All right, so now we're ready to build our model.
So we've got a number of blocks, that's our ship block shapes, and
we have a number of these rectangle offsets, all right.
So that's, we're going to call ROFF.
And the data of those rectangle offsets is just in this array d.
So remember, there's four numbers in every rectangle offset, so
those are the second dimension, one to four.
So every row in this array is basically giving us a rectangle offset.
And then, for each block, we're going to define it as a set
of these rectangle offsets, that's going to give us the shape of the block.
Then we have the width of the river and the maximum length of the river we're
going to be allowed to use to pack our ships in.
So here's some example data.
This is the actual data we need for Cao Cao's problem.
We have five block shapes, we have 12 different rectangle offsets,
the height of the river is 9, and the maximum length we need is 16.
And then you can see, here's all of these rectangle offsets, right,
which are quadruples, basically, xoffset, yoffset, xsize, and
ysize are the four different numbers we have in each row.
And we're sharing some of these blocks in different shapes.
So the five different shapes are defined here, they're sets.
So the first shape is 1,2,3, second 4,5,6,
the third is 5,7,8,12, and 10,11, all right.
As you can see, shape five is used twice.
Now, we have to make the decisions.
So the main decision, of course, is where do we place each block.
So we're going to talk about the x position of the base of the block,
that lower leftmost corner, and the y position of its base.
So those are the main decisions we have to do.
And then the other thing that we're trying to minimize is the length,
the total length of river used, and that's going to be from 0 to max length, and
that's what we're trying to minimize.
So that gives us the base decisions that we need to make in this model and
what we're trying to optimize.
Right, so let's now think about the constraints.
So every rectangle offset in this block shape has to fit within the river.
So we're going to iterate over all the blocks, iterate over all the rectangle
shapes, and pick out the ones which are in this particular block number i.
And if we take the base of block i plus the x offset of this particular rectangle,
and its size and its width in the x direction,
that has to be less than or equal to l.
And then, if we take the y position of the base plus the offset in terms
of the y offset, that's the y base of the rectangle, and
we take its height, it has to be less than or equal to h.
Now we should think, can the rectangle stick out to the bottom of the left?
No, since in our array, we forced all of the offsets to be positive,
so these numbers will always be positive, and
so we'll never have a problem of going underneath.
If we allowed negative offsets, we'd have to add some more constraints to make
sure we didn't stick out the bottom or the left.
If parts of my shape were to the left or
below the 0,0 position we used as our base.
And now the most difficult part is this non-overlap constraint.
And you can see it's very similar in shape to the non-overlap constraint we saw
before, but we have to actually collect the right rectangles.
So we're taking a pair of blocks i and j, and
then we're looking at all pairs of rectangle offsets and
finding the one which is in shape i, and one which is in shape j.
And then we're going to make sure that those two rectangles don't overlap.
And so basically, this is exactly the same thing as we saw before,
but sightly more complicated.
So this x of i plus d of r,1 is the x position of rectangle 1.
And we add its width, and this is the x position of rectangle 2.
So this is basically saying, rectangle 1 is to the left of rectangle 2.
And this very similar formula, it just says, rectangle 2 is to the left of
rectangle 1, or indeed, rectangle 1 is to the right of rectangle 2.
Similarly, here's the formula for the y position of, this is the y position of
rectangle 1 plus its height is less than or equal to the y position of rectangle 2.
So that's saying rectangle 1 is below rectangle 2.
And this similarly says rectangle 1 is above rectangle 2.
And so one of those four possibilities has to happen for our non-overlap constraint.
All right, so we can solve our model.
And here is our solution, packing our ship blocks together.
And if we sort of visualize that from above, you can see,
we've done a much better job.
We've managed to pack some of these ships together tightly,
there's still a lot of space, because they're complicated shapes,
but we've managed to pack it into much less length in the river.
And so it's going to be a much more stable arrangement.
So this is an example of a complex packing problem, right.
So we have shapes, and the way we do that is we make the shapes from components, and
then ensure the components don't overlap.
It's very hard to reason about arbitrary shapes.
So an example of a kind of complex packing problem like this without rotation,
so we haven't considered rotation, we're going to consider that next,
is packing bulk mineral cargoes into storage pads at ports.
So there the shapes aren't that complicated, but
we definitely have to do this rectilinear packing.
As I said, the problems will get much more complicated when we allow orientation,
rotation to be taken into account, and that's what we'll look at next.
