3
$\begingroup$

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

Inefficient Bin Packing

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.

$\endgroup$
1
$\begingroup$

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:

trivially-bad packing

$\endgroup$
  • $\begingroup$ I want to avoid look-ahead because the current algorithm works well enough the vast majority of the time. I only want to back track if there is a lot of whitespace left at the end, which is relatively easy to detect. As for the packing failure you found, I'm not sure how you got that, but I've seen it happen with fractional pixel widths. You can see it packed properly here: codepen.io/anon/pen/GpWgRy $\endgroup$ – Old Pro Oct 1 '15 at 22:08
  • $\begingroup$ It's browser-specific, then, "yay". Because on my browser (Pale Moon x64) the link you sent me has the exact same problem. (I visit that link and the packed automatically version looks the same as the one in my answer) $\endgroup$ – TLW Oct 2 '15 at 12:21
  • $\begingroup$ And you could keep track of the current largest increase in size (i.e. next.size - cur.size) and abort to there and retry with the swap only if you get to the end and there's a lot of whitespace. $\endgroup$ – TLW Oct 2 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.