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.
