Real Life Maths – Bin Packing

Bin Packing

We have to fit a number of boxes of the same width and depth but different height into a rack. The rack is the same depth, divided into slots of the same width and of a fixed height.
There are 11 boxes, A to K, with heights as below

A – 8, B – 7, C – 4, D – 9, E – 6, F – 9, G – 5, H – 5, I – 6, J – 7, K – 9

The rack is 15 units high and we stack the boxes one on top of each other using as few slots as possible.

Similar problems might be cutting lengths of wood from standard lengths, or fitting vehicles into lanes on ferries. In each case we are trying to make the best possible use of the space available and avoid waste ( in the form of unused space above, off-cuts of wood and unfilled lanes).

These problems can be solved by trial and error, but it is worth looking for a more systematic approach (an algorithm).

For the Bin Packing problem there is no known algorithm that will always produce an optimal solution. There are many algorithms that find a good solution – known as heuristic algorithms.

Three are

I. Full-bin algorithm

Look for combinations of boxes to fill bins. Pack these boxes. For the rest place the next box to the next available space.

II. First-fit algorithm

Taking the boxes in the order listed, place the next box to be packed in the first available space.

III. First-fit decreasing algorithm

Reorder the boxes in decreasing size. Then apply the first-fit algorithm to this reordered list.

A method you could use for the first-fit or first-fit decreasing algorithm is:

Define a list of numbers, P, for the heights of the packages (ordered if necessary)

For the bin-packing example, P = {8,7,4,9,6,9,5,5,6,7,8}

Define a second set of numbers, B, for the space remaining in the bins. At the very worst this list will need to be as long as the list of packages.

For example B = {15,15,15,15,……}

Step 1. Take the first entry in P.

Step 2. Is it less than or equal to the first entry in B? Yes – Step 4

No – Step 3

Step 3. Go to the next B entry. Is it less than or Yes – Step 4

equal to this entry in B? No – Step 3

Step 4. Reduce the B entry by this amount.

Step 5 Any more entries in P? Yes – Take the next entry go to Step 2

No – Stop

The result in applying this algorithm is

P = {8, 7, 4, 9, 6, 9, 5, 5, 6, 7, 8}

B = {15,15,15,15,15,15,……}

7, 11, 9, 10, 9, 7

0, 2, 0, 5, 2

You can see how many bins have been used and how much free space there is in each and what packages are in each bin.

For more real world maths problems, you’ll find many online.  One of our favorite resources is the BBC Bitesize site, which at the time of writing has lots of these sorts of problems and other maths resources.   Most of them should be available internationally however much of the website is geo-restricted i.e you’ll not be able to access directly with US residential IPs. There is a solution to this though by hiding your real location using a proxy or VPN you can bypass these sorts of blocks – there’s an example in this post about downloading from the BBC abroad.