0:02

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.

Â 1:42

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.

Â 2:07

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.

Â 2:35

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.

Â 3:30

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.

Â 4:28

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.

Â 4:50

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.

Â 5:56

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.

Â 6:53

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.

Â 7:23

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.

Â 8:34

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.

Â 10:20

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.

Â