Easiest improvement on first-fit for bin packing algorithm

Question

See the interactive example here. First-fit on the left, optimal on the right.

I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the lowest cost improvement over the current solution.

The problem is the one most of the web pages on the internet have: How to best pack a set of rectangles into an enclosing rectangle, preserving order, with no overlaps. Actually the enclosing rectangle is only a fixed width, it expands to arbitrary height needed to fit all the rectangles, but we still want everything aligned along the top.

Real web browsers do it by relying on a rather restrictive set of rules, one of the most significant of which is that the items are presented in a given order and that order must be maintained when laying out the items in the same way text is laid out, which for English is left-to-right, top-to-bottom.

For some cases, though, such as a set of images, the order could be changed somewhat in order to achieve better packing. We do want to limit the reordering, so that an item ends up no more than n places out of position, but we don't need n to be zero.

A web library called Packery implements this with a basic first-fit algorithm. With "gravity" pulling the rectangles to the top-left, it places the first item where it will fit, which of course is the top-left of the enclosing rectangle. It then places the next item where it will fit, and so on, until all the items are placed.

This works very well when the rectangles are all related by small integers, e.g. 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, 3x3, with the enclosing rectangle being some integer width, and there are enough small rectangles. In our example the outer rectangle is 3 units wide. Our inefficient packing algorithm on the left becomes optimal on the right with the addition of just 2 more rectangles that match the voids.

So the question is: is there a low-cost way to detect the inefficient packing and backtrack or make some other alteration to get to the efficient packing in the middle? Keep in mind that we want to preserve order as much as possible, so the optimization of pre-sorting the list so that the largest rectangles are first is not acceptable.

Answer 1

One "easy" option is to, after the first-fit algorithm has run, do a local search, i.e. checking if there are any k swaps / moves that you can do to improve the packing (i.e. removing a row or column) (for a relatively small value of k).

I also suspect, although this isn't rigorous by any stretch of the imagination, that you could, to a specified maximum depth, do a search-and-backtrack with the current element and next element every time you hit an element that is larger than the next element. In this case, for instance, you have the elements [1x1, 2x1, 1x1, 1x2, 1x3]. You specify a maximum depth, say 1. Then you start packing elements. In this case just packing [1x1] so far. When you hit the 2x1, you try packing [2x1, 1x1, 1x2, 1x3], , but you also branch and try packing [1x1, 2x1, 1x2, 1x3]. Ideally with an alpha-beta search, but you can also just try going to a specified lookahead and then seeing which is better.

Also, note that that particular packing library has... issues. In particular, when you tell it to pack [1x1, 1x1, 2x1, 1x2, 1x3] it does this: