t’s easy to list applications where computers leave humans in the dust. When it comes to complex mathematics, repetitive calculations, and tedious searches, even the most astute mathematician can’t beat a good computer program.
However, there are also many applications where humans can easily surpass computers. For example, some classic problems that have only recently yielded to high-powered hardware and sophisticated algorithms are pattern matching applications such as face recognition, speaker-independent speech recognition, and chess.
Another problem that’s usually easier to solve for people than computers is two-dimensional bin packing (2BP). The idea is that you have some sort of area or stock that you need to fill with as many items of given sizes and shapes as possible.
|Figure 1. Rotated Arrangement: You can see that the only way to fit these five squares on the stock without an overlap is to rotate the center square.|
For example, suppose you have several sheets of plywood from which you want to cut a set of shapes. The goal is to cut out the pieces using as few sheets as possible. If you were cutting 1×8 ft. strips from a 4×8 sheet of plywood, the problem would be easy, but when the shapes aren’t regular, or the substrate isn’t a multiple of the shape size, the problem becomes deceptively difficult, and has a huge number of variations. Some of the variations include:
- You are allowed to rotate the pieces arbitrarily, allowing an infinite number of possible positions and orientations. Figure 1 shows five squares positioned on a larger square. The center square will not fit unless it’s rotated as shown.
- You are allowed to rotate the pieces?but only in certain restricted ways, such as in multiples of 90 degrees.
- The pieces must have fixed orientations. For example, pieces might need to be oriented along the wood grain. If the stock is cloth, you might need to orient pieces along the cloth’s pattern or weave. As an example, in one M*A*S*H episode Trapper John buys a pinstriped suit, but the tailor makes it with the stripes sideways. In such cases, you may be able to rotate the pieces by 180 degrees but not to other angles.
- Pieces may be concave. For example, a series of crescent shapes could be nested inside each other to take up less room.
- You are allowed to cut up the stock using only “guillotine cuts” that go from one side of the stock to the other. For example, suppose you need to cut up a piece of wood using a table saw that cannot cut corners.
- You are loading objects into a truck. In addition to fitting as many objects in the truck as possible, you may also need to distribute their weight evenly. You may need to place heavier objects as close to the center as possible, or you may need to place heavy items near tie-down points.
Rather than having fixed-size sheets of stock, you have a long continuous sheet such as a bolt of cloth. In this case, the goal isn’t to use as few sheets as possible, but to use as little length as possible.
The problem is difficult enough in two dimensions, but the problem gets even trickier in three-dimensional variations. Imagine trying to pack several hundred experiments inside the space shuttle. Or imagine trying to arrange hundreds of thousands of items on a cargo ship. With so many possible arrangements, it’s no wonder shipping companies simplify the problem. For example, container ships carry thousands of huge metal containers that all have the same size and shape, regardless of their contents. You may still need to worry about weight distribution, but having fixed-size regular shapes, makes the packing problem much more manageable.
Solving a Simple 2BP Problem
This article discusses some approaches for solving one of the simpler variations of 2BP, using these assumptions:
- The shapes are rectangles with sides of rational lengths.
- You cannot rotate the shapes.
- The stock has a set width but is infinitely long. You can think of it as an idealized bolt of cloth or roll of paper.
One way to solve this problem is to exhaustively try every possible arrangement for the shapes. If their sides have rational lengths, then you can find the smallest distance that divides evenly into all the shapes’ side lengths, and use that to determine all the positions where the shapes might need to go.
For example, if every shape has sides measured in an integer number of inches, you can divide the stock into a grid of one-inch squares. To enumerate every possible location for the shapes, you would try placing each shape so its upper-left corner lies in every square.
Here’s why the problem is difficult. The number of possible allowed combinations depends on the size of the stock and the exact sizes of the shapes, but you can get some idea of how big the problem is by ignoring the sizes of the shapes altogether! For example, suppose the stock is 10 inches wide, you have 8 shapes, and you consider only a 20-inch length of the stock. Then the stock contains 10 * 20 = 200 squares where you could (theoretically) place each of the 8 shapes. There are 200 possible positions for the first shape, 199 for the second, 198 for the third, and so forth. The total number of combinations is 200 * 199 * … * (200 – 7), which is roughly 2.2E18. If you could evaluate one million of those combinations per second, it would take you more than seventy thousand years to check them all.
In practice the situation isn’t quite that grim. For example, the preceding calculation doesn’t exclude overlapping shapes, or that shapes placed too close to the right or bottom edges of the stock will lie partly off the edge. However, it does give you a sense of how many possible solutions there might be. If you eliminate all the illegal arrangements, you may be able to exhaustively examine all of the possible solutions for eight shapes?but you still won’t be able to handle problems that are much larger. In other words, an exhaustive search is possible only when there are fewer than eight or nine shapes; for larger problems, you’ll need to use heuristics?algorithms that are likely to give you a good solution but are not guaranteed to produce the best possible result.
For example, one heuristic for getting somewhere as quickly as possible is to drive five miles per hour over the speed limit. There’s some chance you’ll get a ticket for speeding, but the odds are you’re safe as long as you’re not doing anything else naughty at the time. You might be able to go a little faster, but then the odds of your being pulled over increase?and a traffic ticket will definitely delay your arrival.
|Figure 2. Two Columns Heuristic: This heuristic divides the stock into two columns, placing the widest rectangles first, and attempting to place the next rectangle in the shorter of the two columns.|
The 2BP program example (see Figure 2) that you’ll find in the downloadable code in both Visual Basic and C# versions, demonstrates several heuristics for solving 2BP. Enter the width of the stock in the “Bin W” text box on the upper left. Enter the dimensions of the shapes in the “Inputs” text box. Then click one of the buttons to run a particular algorithm.
This article describes most of these algorithms in words rather than code, but you can download the project example and look at the code to learn the programming details.
Figure 2 shows the solution found by the “Two Columns” heuristic described in the following section. You can easily see that this solution isn’t perfect. You could slide the 3×2 rectangle at the bottom into the open area to the right of the 6×6 rectangle to reduce the total height by 2 units. You could then move the 4×2 rectangle next to the 6×6 rectangle and move the 2×3 rectangle into the upper right corner, shortening the solution to a height of 14. You may want to experiment for a few minutes to see if you can come up with a better solution.
Two Columns Heuristic
The Two Columns heuristic is one of the classic algorithms for solving 2BP. It was written up by Stanford’s Daniel Sleator in Information Processing Letters way back in 1980.
First the heuristic removes any shapes that are wider than half of the stock’s width and places them at the top of the stock. In Figure 2 these are the rectangles with dimensions 8×3, 7×1, and 6×6.
Next the algorithm divides the stock into two equally sized vertical columns. It then sorts the remaining shapes by height with the tallest first.
The algorithm places the tallest shape in the first column, which begins a horizontal strip with the height of this first item within the column. The program places the subsequent shapes next to the first one (in order of decreasing height) until no more shapes will fit in the strip.
Now the program considers the two columns and determines which one has the smaller total height so far. It places the next item in that column and starts a new strip. The program continues filling strips and then starting new strips in the shorter column until it runs out of items. Figure 2 shows the result. The red “18” at the bottom describes the total length of stock used.
This algorithm isn’t the best possible alternative, but it is useful because it sets an upper bound on how tall the piece of stock must be. Sleator’s paper shows that, if Halg is the height given by the algorithm, Hopt is the optimal solution, and Htall is the height of the tallest rectangle, then:
Halg <= 2 * Hopt + Htall / 2
The algorithm provides only a loose boundary, but it's better than simply adding up the heights of all of the rectangles.
One Column Heuristic
One problem with the Two Columns heuristic is that two adjacent strips may together contain enough empty space to hold another shape. For example, if you slide the 4x3 rectangle left so it's next to the 4x4 rectangle in Figure 2, then you can fit the 2x3 rectangle next to both of them. Splitting the stock into two vertical columns makes it easier to prove the bound on the optimal solution, but doesn't necessarily give you the best arrangement.
The One Column heuristic begins just like Two Columns, by positioning the rectangles that are more than half the width of the stock. However, instead of dividing the stock into two vertical columns, it then fills the stock in a single column. It positions the next tallest item to make a horizontal strip and then uses subsequent rectangles to fill the strip.
|Figure 3. One Column Heuristic: Using one column produces a better result in this case.|
The result, shown in Figure 3, is an improvement over the Two Columns heuristic, at least in this example. Even in this solution, however, you can see lots of unused space in the upper parts of the solution and it's easy to see how to improve the solution. The algorithm would produce a better solution if it simply treated the first few extra-wide rectangles like it does all of the others and filled in their horizontal strips as much as possible.
Sort and Fill
The next few heuristics improve on the One Column algorithm by treating every rectangle the same way. They sort the rectangles in some manner and then start laying them out in horizontal strips.
The Sort by Height heuristic sorts the rectangles by height. It places the first in the stock's upper-left corner and starts laying out subsequent rectangles next to it until no more fit. It then starts a new horizontal strip and continues until all of the rectangles are in position.
|Figure 4. Sort by Height: This algorithm fits all the rectangles into only 14 units of stock.|
Note that this algorithm does not simply try to fit the next rectangle in a strip; when the next rectangle won't fit, this algorithm tries the following rectangles to see if any of them will fit. This approach lets it fill in areas such as the ones to the right of the 8x3 and 6x6 rectangles in Figure 3.
Figure 4 shows the Sort by Height algorithm's result. This version manages to fit all the rectangles into only 14 units of stock, considerably better than the 16 given by One Column and much better than the original height of 18 given by Two Columns.
The following code shows how the main algorithm works. It starts by using the Array.Sort method to sort the rectangles by height. The HeightComparer class provides a Compare method that compares rectangles by their heights and lets Array.Sort sort them properly. (The code also includes WidthComparer, AreaComparer, and SquarenessComparer classes used by other algorithms in the project.) After it sorts the rectangles, the code calls the SubAlgFillOneColumn method.
' Sort rectangles by height. ' Fill in by rows in a single column. Public Sub AlgSortByHeight(ByVal bin_width As Integer, _ ByVal rects() As Rectangle) ' Sort by height. Array.Sort(rects, New HeightComparer) ' Fill in one column. SubAlgFillOneColumn(bin_width, rects) End Sub
The following code shows how subroutine SubAlgFillOneColumn works.
' Fill in by rows in a single column. Public Sub SubAlgFillOneColumn(ByVal bin_width As Integer, _ ByVal rects() As Rectangle) ' Make lists of positioned and not positioned rectangles. Dim not_positioned As New List(Of Rectangle) Dim positioned As New List(Of Rectangle) For i As Integer = 0 To rects.Length - 1 not_positioned.Add(rects(i)) Next i ' Arrange the rectangles. Dim x As Integer = 0 Dim y As Integer = 0 Dim row_hgt As Integer = 0 Do While not_positioned.Count > 0 ' Find the next rectangle that will fit on this row. Dim next_rect As Integer = -1 For i As Integer = 0 To not_positioned.Count - 1 If x + not_positioned.Item(i).Width <= bin_width Then next_rect = i Exit For End If Next i ' If we didn't find a rectangle that fits, ' start a new row. If next_rect < 0 Then y += row_hgt x = 0 row_hgt = 0 next_rect = 0 End If ' Position the selected rectangle. Dim rect As Rectangle = not_positioned.Item(next_rect) rect.X = x rect.Y = y x += rect.Width If row_hgt < rect.Height Then row_hgt = rect.Height ' Move the rectangle into the positioned list. positioned.Add(rect) not_positioned.RemoveAt(next_rect) Loop ' Prepare the results. For i As Integer = 0 To positioned.Count - 1 rects(i) = positioned(i) Next i End Sub
The code starts by building two lists: one holds the rectangles that are positioned, and the other holds those that aren't positioned yet. Initially the not_positioned list holds all of the rectangles and the positioned list is empty.
The code then enters a loop that executes as long as there are rectangles that have not yet been positioned. The code looks through the not_positioned list in its sorted order to find the next rectangle that will fit in the current strip. If the code doesn't find a rectangle that will fit, it starts a new horizontal strip. We know that the first rectangle in the not_positioned list will fit on the new strip because that strip is currently empty.
The code positions the selected rectangle, either in the old strip or in a new one, and moves the rectangle from the not_positioned list to the positioned list.
The loop continues until every rectangle has been positioned. The algorithm then copies the rectangles back into the rects array to return the results to the caller and exits.
|Figure 5. Sort by Width: This algorithm uses a one-column arrangement and sorts the rectangles by width.|
The Sort by Height heuristic does a pretty good job of filling up empty areas, but there's still potential for improvement. The algorithm is remarkably simple so it's worth taking some extra time to see if other variations will produce useful results.
The Sort by Width, Sort by Area, and Sort by Squareness algorithms work exactly as Sort by Height does except they sort the rectangles differently before moving them into horizontal strips. These algorithms use different Comparer objects to sort the rectangles, but are otherwise identical.
Sort by Width sorts the rectangles by width. The arrangement differs from that produced by Sort by Height, but the total height is the same (see Figure 5).
Sort by Area sorts the rectangles by their area and positions the largest first. The idea is that the largest rectangles create empty areas that are hard to fill completely so it tries to fill them first while there are still smaller rectangles to use. The arrangement (see Figure 6) is again different, but results in the same total height.
Sort by Squareness sorts the rectangles by the differences in their heights and widths so those that are most square are considered first. I didn't really have a great motivation for this one?but it was easy and sometimes you need to experiment. Figure 7 shows the result?no improvement in this case.
If you study Figures 4, 5, and 6, you can find simple ways to improve the solution. For example, in Figure 6 you could move the 3x2 rectangle into the space next to the 6x6 rectangle to reduce the total height by one unit. Unfortunately, the algorithms that fill by strips don't consider this type of solution, because it requires rectangles to be stacked within a strip. In this improved solution, the 3x2 rectangle is stacked below the 4x4 rectangle.
Fill by Stripes
Algorithm Fill by Stripes is more complicated than the previous algorithms. Again, it starts by sorting the rectangles by height. Then it positions the tallest non-positioned rectangle and uses it to start a new horizontal stripe. The algorithm then calls the FillBoundedArea method to fill that stripe as completely as it can by using the remaining rectangles.
FillBoundedArea is a fairly tricky recursive subroutine. It starts with an area to fill (the stripe) and loops through the non-positioned rectangles, placing each rectangle in the upper-left corner of the area it is filling to see whether that placement produces a good solution.
|Figure 8. FillBoundedArea: By dividing empty space into areas determined by the edges of an already-placed rectangle, this method tries to make optimum use of remaining space.|
The subroutine then divides the area either vertically or horizontally along an edge of the newly positioned rectangle, which is in the green area labeled 1 in Figure 8. The subroutine first tries dividing the area horizontally, and then divides the remaining area into the piece labeled 2 and the large horizontal area containing the regions labeled 3 and 4 (surrounded by the red lines). Subroutine FillBoundedArea calls itself to see how well it can fill these two new areas 2 and 3 + 4.
After the recursive call to itself returns, FillBoundedArea tries dividing its area vertically. In Figure 8, it now considers the area labeled 3 and the large vertical area that includes the regions 2 and 4 (surrounded by the blue dashed lines). The subroutine calls itself recursively to see how well it can fill these two new areas 3 and 2 + 4.
When that recursive call returns, the method evaluates whether it did a better job filling the total area by using the horizontal division or the vertical division. Finally, if the better of those solutions improves on the best solution found so far for the total area, it saves the new solution.
|Figure 9. Fill by Stripes: This heuristic recursively attempts to find the best possible solution after placing each remaining rectangle.|
Now the method goes back and tries again, starting with a new rectangle positioned in the upper left corner (area 1 in Figure 8). It iterates over all the rectangles in this manner, placing each, and then recursively filling any remaining empty area until it has tried all the rectangles. When the loop completes, it returns the best solution.
Figure 9 shows the best solution found by the Fill by Stripes algorithm. It's an even better solution than the one found by the Sort and Fill algorithms, having a total height of only 13 units.
The Recursive Division algorithm uses recursion similarly to Fill by Stripes, but where Fill by Stripes starts by positioning a rectangle and then using the FillBoundedArea subroutine to try to fill its horizontal strip as densely as it can, the Recursive Division algorithm does away with the idea of stripes altogether. Like Fill by Stripes it positions a rectangle and then considers dividing the remaining area vertically and horizontally along the rectangle's edges. Unlike Fill by Stripes, however, the lower areas that it must then fill are not always bounded below.
Look again at Figure 8. Suppose the algorithm has just positioned the very first rectangle. This algorithm doesn't use stripes so the total area to fill includes the entire piece of stock, which does not have a fixed length. Imagine that areas 3 and 4 don't have bottom edges; they extend indefinitely downward. The FillBoundedArea method can fill only bounded areas (hence the name) so it won't work on unbounded areas. However, FillUnboundedArea can fill unbounded areas.
|Figure 10. Recursive Division: The Recursive Division algorithm packs rectangles equally as well as Fill by Stripes.|
The Recursive Division algorithm starts by calling FillUnboundedArea to fill the entire stock area. That routine positions a rectangle as before, and tries to divide the area horizontally and vertically. For the horizontal division, it calls FillBoundedArea to fill area 2 and calls FillUnboundedArea to fill the combined area 3 + 4. For the vertical division, it calls FillUnboundedArea to fill area 3 and calls FillUnboundedArea to fill the combined area 2 + 4.
When its recursive calls return, the subroutine considers the solutions it found and returns the best one.
Figure 10 shows the result produced by the Recursive Division heuristic. It results in a new arrangement but the same total height as the Fill by Stripes technique.
If you look closely, you'll see that each solution has a row with 6 used squares. Each solution also has 11 unused squares on other rows. In theory at least, if you could rearrange things to move those 6 used squares onto other unused squares, then you could eliminate the six-used-squares row and shorten the solution by another unit to a height of 12.
That result shows that we cannot prove there is no better solution, but it doesn't tell you whether a better solution is actually possible. In fact, you can achieve a better solution. You might want to spend a few minutes trying to find it before you read further.
For a relatively small problem such as this one, you can resort to exhaustive search. The heart of the sample program's exhaustive search is the FillExhaustive subroutine shown in the following code:
Private Sub FillExhaustive(ByRef best_rects() As Rectangle, _ ByRef best_max_y As Integer, ByVal rects() As Rectangle, _ ByVal next_i As Integer, ByVal used(,) As Boolean) ' See if we're at a leaf node. If next_i >= rects.Length Then ' We're at a leaf node. ' See if this solution is an improvement. Dim max_y As Integer = MaxY(rects) If best_max_y > max_y Then best_max_y = max_y best_rects = DirectCast(rects.Clone(), Rectangle()) End If Else Dim rect As Rectangle = rects(next_i) For y As Integer = 0 To _ used.GetUpperBound(1) - rect.Height + 1 For x As Integer = 0 To _ used.GetUpperBound(0) - rect.Width + 1 ' See if we can put the rectangle here. Dim can_fit As Boolean = True For i As Integer = 0 To rect.Width - 1 For j As Integer = 0 To rect.Height - 1 If used(x + i, y + j) Then can_fit = False Exit For End If Next j If Not can_fit Then Exit For Next i ' Give it a try. If can_fit Then ' Put the rectangle here. rects(next_i).X = x rects(next_i).Y = y For i As Integer = 0 To rect.Width - 1 For j As Integer = 0 To rect.Height - 1 used(x + i, y + j) = True Next j Next i ' Recurse. FillExhaustive(best_rects, best_max_y, _ rects, next_i + 1, used) ' Un-put the rectangle here. For i As Integer = 0 To rect.Width - 1 For j As Integer = 0 To rect.Height - 1 used(x + i, y + j) = False Next j Next i End If Next x Next y End If End Sub
The best_rects parameter is an array containing the current best solution, while best_max_y is the height of that solution. The rects array contains all the rectangles; next_i is the index of the next rectangle that the algorithm must position. The used array holds one entry for each square in the stock and contains true if a square is in use by a rectangle.
The code starts by checking whether every rectangle has been positioned. If so, it's reached a possible solution. The code compares this solution's best_max_y value to others and saves this solution if it improves on the previous best solution.
If all the rectangles have not yet been positioned, then the code tries placing rectangle number next_i in every possible position. The code loops through each possible X and Y position, skipping coordinates where the rectangle would fall partly off of the stock's right or bottom edge. For each possible position, the code tests the used array to see if the rectangle can fit without overlapping another previously positioned rectangle.
When a rectangle can fit at a position, the subroutine puts it there, updates the used array, and recursively calls itself to position the remaining rectangles.
|Figure 11. Exhaustive Solution: By testing every possible arrangement, the exhaustive solution finds the best possible answer.|
After the recursive call returns, the subroutine removes the rectangle from its position and continues its loop, trying to place the rectangle in other locations.
When the original call to position the first rectangle finishes, the program has tried every possible arrangement of the rectangles and has found the best possible solution. Figure 11 shows the result?with a total height of only 12 units. This solution contains only 5 unused squares and the emptiest row contains 7 used squares so I'm fairly confident that you won't be able to find a better solution than this one. Table 1 summarizes the results of the heuristics you've seen.
|Sort by Height||14|
|Sort by Width||14|
|Sort by Area||14|
|Sort by Squareness||15|
|Fill by Stripes||13|
The first several, Two Columns through Sort by Squareness, are relatively straightforward and produce fairly good results, but their main advantage is that they're also extremely fast, so your best bet is to try them all and pick the best result.
The Fill by Stripes algorithm is much more complicated and requires some fairly tricky recursion, so it takes longer than the previous algorithms, but it's fast enough that speed isn't much of an issue. In one test, the first few algorithms took no noticeable time to arrange 50 rectangles, while Fill by Stripes took about 0.30 seconds.
Recursive Division uses a much more complete recursion, so it takes some serious time. One test took 38 seconds to position only 10 rectangles.
Finally exhaustive search takes the longest. In one test this algorithm took 45 seconds to position a mere eight rectangles. You can see that it's probably not possible to use an exhaustive method to position more than nine or ten rectangles in a reasonable amount of time.
Other heuristics are certainly possible, and you may be able to come up with some that beat these algorithms at least some of the time.
For any given stock width and collection of rectangles, different heuristics will produce different results. To get the best results, try the fastest algorithms first, and pick the best solution they produce. Then if you have time, rewrite the Recursive Division and Exhaustive algorithms so they display good solutions as they find them?and let the programs rip. Then, at any point during execution, you can decide whether the current best solution is good enough, or whether you want to wait and give these slower algorithms a chance to find even better solutions.
It's also possible that other heuristics will find better solutions for certain arrangements of shapes. If you discover any that work well, let me know and I'll make them available on the VB Helper web site.