2.4.3 Rectilinear Packing with Rotation

Loading...

Do curso por The University of Melbourne

Advanced Modeling for Discrete Optimization

46 classificações

The University of Melbourne

Advanced Modeling for Discrete Optimization

46 classificações

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

Na lição

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.

2.4.1 Square Packing16:18

2.4.2 Rectilinear Packing without Rotation11:06

2.4.3 Rectilinear Packing with Rotation15:21

Conheça os instrutores

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
Computing and Information Systems

Zhuge Liang wasn't satisfied with the solution provided by the tablet.

He just realized that he had not factored in that the ship blocks could be rotated.

He discussed the possibility of reducing the overall length of the large block by

using rotations with Pang Tong, who agreed.

Zhuge Liang pulled out the tablet to try to work out a new solution.

[SOUND] >> So,

Pang Tong came to Zhuge Liang to find out how to pack his ships together.

But when Zhuge Liang saw the answer that came out of the model, he said, well,

look, I'm sure we could do a more compact packing,

if we also considered rotating these ship blocks.

So, let's look at how to do that.

So, in a rectilinear packing, a shape can have four orientations normally.

So, if we take this object we could rotate it by 90 degrees, that would give us this,

or 180 which would give us this or 270 which would give us that.

So, obviously more complicated packing problems, I can rotate any amount

that's a much more complicated packing that we'll look at in this course.

So, we have to be aware that some of these orientations don't make any sense for

some shapes.

See, if I have a plain rectangle, there's only really two orientations.

So, I can have the rectangle like this or like this, but

then doing this is just the same as the original orientation.

So, there's only really two orientations.

And similarly, a square only has one orientation.

Doesn't matter how I rotate it, it's still going to be the same square.

And there might be application-oriented restrictions.

We might want our block of ships to be able to move up and down the river, and

maybe there's a direction that we have to keep.

So, maybe only that way or that way would be sensible.

So, we've already seen how we're representing block shapes.

So, this is exactly what we saw in a previous lecture.

Let's think about representing orientation.

So, a new orientation is really no different than a new block shape.

So, if I take this rectangle offset block shape here and

I move it over here and rotate it, then really all I've got is another

orientation, a new set of shapes with offsets.

And indeed, I can just, here is our new base, and now I can introduce

these new rectangle offsets to represent the rotation of this shape by 90 degrees.

And you can see that he offsets can change quite dramatically, whereas, of course,

the dimensions will just flip if we've flipped the thing by 90 degrees.

So, we don't need anything new to represent orientations of this shape.

So, here's the original orientation of the shape.

And then, if I've rotated it 90 degrees,

here's another representation of this shape as the rectangle offsets 2,5,6.

All right, so we can represent our shape as basically a set.

So, an orientation is a set of these offsets and

then a shape consists of the 4 different possible orientations.

Or less if it's a shape where it doesn't make sense to rotate it that many times.

So, basically we're going to represent a shape as a list,

an array, of sets of offsets.

All right, so just before it was a set of offsets,

now it's a list of those for each possible orientation.

And we can represent duplicated or

forbidden orientations by just having an empty set in that position.

So, let's now get back to our ship block packing problem again, but

now allowing rotations.

So, we're going to highlight what's different.

So, nothing else has changed here, we've got the same set of rectangle offsets as

before, there's probably going to be more as we'll see there in the data.

Of course, we have different rotations and now here's the key difference, that

a block, we have for each rotation, a set of these rectangle offsets.

Which is giving us the shape of that block and of that rotation.

All right, so rather than just having a single set of rectangle offsets for

the block, now we've got four, one for each different rotation.

And now, here's the diagram, you can see,

that we've got many more of these rough rows in the array.

But, otherwise nothing's changed, and here is the new thing.

So, basically for each shape, we have the four different orientations

that we could use to represent that shape and its different rotations.

And for the shape, which only two of them made sense,

we've put in these empty sets to say, you can only really rotate it

by 90 degrees, which is equivalent to rotating it 270 degrees.

So, this is the new data to represent the rotatable shapes.

So now, we go back to our decisions,

they're just the same as before except, of course, for

each block, we have to choose which rotation to use, nothing else has changed.

And we have to again, well this is new, we have to say,

but we can't use these disallowed configurations.

So, for every shape, we're looking at, for that particular rotation, if we get

an empty set then that's not a rotation we should have used for that shape.

So that's simple.

And then we have to make sure that every rectangle offset in the block for

the rotation we picked fits within the river.

So, this is exactly the same constraint as we saw before.

But rather than taking r in the shape of i,

which was just this particular one way that I could represent this shape.

Now I'm picking r, all the rectangles in the shape of i for the given rotation.

And everything else just stayed the same.

All right, and again, the non-overlap constraint is the same.

Nothing has changed here, except, we're not picking these r1 and r2,

this is a rectangle from block i and this is a rectangle from block j.

I just have to pick the rectangles which are in the particular rotation of that

block, the shape of that particular rotation.

Similarly for picking r2 from the shape of j in the rotation we chose for j.

And then the non-overlap constraint for

the rectangles is just exactly the same as before.

So, now we can solve our model.

It takes 1 minute and 30 seconds, so it's bit more difficult but

we've now got a much more compact packing of all our ship blocks.

So, you can see it here,

we've managed to fit it in 1100 meters of width in the river.

So, of course, you might have guessed that if we have a complex problem like this,

it's come up many times.

So, there are more packing globals which can help us.

So, there's the diffn_k global, which extends diffn,

which was 2D packing to k dimensions, an arbitrary number of dimensions.

But the one we're going to concentrate on is the geost global constraint,

which allows you to enforce non-overlap of objects

where they take different configurations into account.

So, we're going to use those different configurations to represent the different

rotations but there could be other reasons that we have different rotations,

different configurations for an object we might be able to slide parts apart or

repack the object in different ways.

So, our objects can have multiple possible shapes, we'll use that

to represent different rotations and each shape is a set of offset rectangles.

So, it's using exactly the same kind of ideas as we've seen in the models so far.

So, here is the geost bounded constraint.

So, this is one version, is a number of geost constraints, but this is the one

we want, because it's taking into account the bounding box of the entire thing.

So, let's look at its arguments.

The first argument is the number of dimensions for

the packing problem we're doing.

So, we're going to be using two, but it could be three, or four, or five.

And then we have the rectangles that we're going to make up.

So, this is basically,

the r of these two arrays are going to be the ROFF array, broken into two parts.

So, this is the sizes of the rectangles, and of course,

the second dimension is going to be equal to 1 to k.

So, in two dimensions, it'll two numbers in each row of this thing,

if we're doing three-dimensional packing, it'll be three numbers, and

we'll be representing the, sort of boxes.

Then the rectangle offsets again will have k dimensions.

Each row will be a rectangle offset with k dimensions.

And then a shape is a set of these ROFFs, just as before.

So, basically these integers are pointers into these arrays of size and offset.

So here, before we used a single array to keep these things,

here because it's k dimensions, we want to keep them in two different arrays because

we don't know the second dimension.

Now, the key thing is, this is the positions where the objects go, right?

And those objects are going to pick a shape.

So, again the second dimension here is going to be the number of dimensions.

So, rather than have an x and a y because we're doing two dimensions,

now we're going to have a two-dimensional array,

which this number of coordinates could be any number.

And then the critical new thing is this kind choice.

So, for each object, we're going to pick which kind, so

which shape, how we're going to use?

So, basically this is an index into this array

telling us which shape we're using for this object.

And the last two arguments are just lower and upper bounds on all the objects.

So, they have to fit within the box with these lower bounds and these upper bounds.

So, there's one dimension here for each of the k dimensions that we need.

All right, let's build our model using geost.

Now we can actually take the same data input and do geost but

it takes a bit of effort, so we're going to take an easy approach and

just modify the input data slightly.

So, the Geost Data File looks exactly the same up to now, so

we're doing exactly the same as we've seen before.

But we're going to take our shape, which was a two-dimensional array, and

just write it as a one-dimensional array, effectively.

And get rid of the empty sets, because they're not going to be very interesting.

And then we're going to recover, basically,

information which was in that two-dimensional array for rotations,

by just saying, so object 1 can take shape 1, which is this set of ROFFs,

or shape 2 which is this one, or shape 3, or shape 4, right?

So, it's basically,

it's the same as we used to have with the two dimensional array.

And this is more efficient in some sense because here,

you notice, the empty sets are gone, they're not interesting.

And when we look at object 4, it can take either this shape or this shape.

And only two possibilities.

So, let's fix our model up, let's concentrate on the changes.

So, rather than having this, so now we've got this inset of these ROFFs.

Right, rather than a two dimensional array, we have one.

And now we have to take our, so our data has given as d,

which is each row has four numbers in it.

We have to break it into the two arrays of two numbers that the geost expects.

So, it expects the sizes, which is basically the positions 3 and

4 in our two dimensional array.

And expects the offsets,

which is positions 1 and 2 in our four dimensional array.

So, we're just building up the right data that the geost expects.

We also have to build our coordinate array, a two dimensional array, rather,

we've used, we're going to use x and y so, we need to make this into a single array,

a two dimensional array.

So, x is the first coordinate and y is the second coordinate.

That's just building the argument that geost expects.

Finally, the interesting part is for every block, we've got this kind.

So, this is which particular orientation of the block we pick.

And so for each block, we have this possible shapes that we could pick and

basically this kind is going to pick one of these shapes.

So, for every block, we make sure that the kind that we pick for this shape and for

this block is one of the shapes in its possible shapes.

So, these shape indexes, remember,

represent all the possible rotations of that ship block.

Once we've one that, basically,

we just have one geost constraint doing everything, right?

We're doing two dimensional packing, here's the size arrays,

here's the offset arrays.

Here's our definition of all the possible shapes we can do.

Here's the coordinates of the objects, and here's the kind of each object.

And here is the lower and upper bounds.

So, our lower bounds is [0, 0], and our upper bounds are the length we're

allowed to use and the height of the river.

And then geost will do everything.

And unsurprisingly,

if we now run the model, we're going to get a lot faster solution.

We've found a different solution but it's equally good.

So, a different optimal solution popped out.

But using the global, it was much more efficient.

So, what we've looked here in this ship block packing problem may seem

very obscure but

actually what we've seen is really an example of carpet cutting problem.

So, in carpet cutting, we need to measure each room size and shape and

we basically make a rectilinear version of the shape.

Then we have to cut the carpet out of a roll of carpet of fixed width, so

that's our river.

Then we can lay that carpet down.

And of course, the less length of the roll that we use, we use less wastage and

basically that means more profit to the carpeting company.

Because they have to pay for all the roll that they cut, and you only pay for

the area of carpet that is laid.

Now, the real problem is, it has lots of complexities.

We'll talk a bit about carpet direction but there's also stairs which can be cut

lots of different ways, and filler carpets and other constraints.

So, one thing comes from carpet orientation.

If we had just a plain, uniformed carpet,

then we can cut it in all four ways because it's going to look the same.

But, if we take a carpet with some pattern in it, then we've got to be more careful.

So basically, a patterned or

horizontal striped carpet, we can really only cut it in two ways.

We can cut it this way or we could invert the shape and cut it like this.

If we cut it a different way then the stripes will be going in

the wrong direction.

And then, if we take a non-symmetric patterned carpet then really,

there's only one way we can cut it, so

that all of the rooms will have the carpet right in the same way.

So, in summary, we have looked at more complicated packing problems here.

So, we're basically using the same tricks.

We make out shapes from components, and we ensure the components don't overlap.

And rotations and orientations add complexity of the problem,

but they're not that much more difficult.

Basically, we add a new level of decision, which is which orientation for

each shape we're going to use.

And then we make sure that particular orientation doesn't overlap

with anything else.

And we didn't look at, but told you about diffn extension for k dimensional packing.

And we've showed you the use of geost which is for

flexible k dimensional packing.

And indeed, in practice, the most packing is either 2D or 3D, so

we typically don't use these things for dimensions beyond that, occasionally 4D.

But very rarely beyond that.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play