Created: 15-OCT-2009. Last Modified: 19-MAY-2013

Bin Packing is a common type of problem. It comes in all kinds of shapes and forms.

One example is a transporting company that ships containers oversea. The containers have a fixed capacity. The goods ships have different dimensions. Therefore the allocation of the goods to the containers is very important, because additional containers incur (high) additional cost.

Another example is to cut cable to the right size. Any remainder of a cable is waste and (depending on the cable) can be very costly.

There are many other examples that requires a solution to the same problem: to reduce waste.

## The solutions

This series of articles shows different approaches to the bin packing problem, in search of
the "best" solution:

One example is a transporting company that ships containers oversea. The containers have a fixed capacity. The goods ships have different dimensions. Therefore the allocation of the goods to the containers is very important, because additional containers incur (high) additional cost.

Many packages in many sizes.

Ship all of them

in as few bins as possible!

Ship all of them

in as few bins as possible!

Another example is to cut cable to the right size. Any remainder of a cable is waste and (depending on the cable) can be very costly.

There are many other examples that requires a solution to the same problem: to reduce waste.

- Solution 1: Start to Finish, no looking back
*(Simplest code)* - Solution 2: Start to Finish, but with looking back
- Solution 3: Start to Finish, looking back, in groups
*(Simplest scalable solution)* - Solution 4: Combination matching, fewest first
- Solution 5: Combination matching, fewest first, optimized
*(Fastest solution for perfect set)* - Solution 6: Combination matching, most wasteful first
*(Best solution for imperfect set)* - Solution 7: Brute force discovery for few packages
*(Find maximum set)* - Solution 8: Brute force discovery for many packages
*(Find maximum set robust)*

The bins have a maximum capacity of 100. Each package has a size of anywhere between 2 and 60.

Here is the definition of the bins table. Since this series of articles discussed several different solutions, it has a column called Solution to indicate the solution that was used.

CREATE TABLE dbo.bins (solution tinyint NOT NULL ,bin_no int NOT NULL ,space_left smallint NOT NULL ,CONSTRAINT PK_bins PRIMARY KEY (solution,bin_no) ) -- helper index CREATE INDEX IX_bins ON dbo.bins(space_left)

The script that populates the packages table uses a numbers table. So the code snippet starts off with the creation and population of this helper table.

CREATE TABLE dbo.numbers (n int PRIMARY KEY) INSERT INTO dbo.numbers VALUES (1) Declare @i int Set @i=1 While 100000 > @i Begin INSERT INTO dbo.numbers SELECT n+@i FROM dbo.numbers Set @i=@i*2 End CREATE TABLE dbo.packages (package_no int IDENTITY PRIMARY KEY ,size smallint NOT NULL ,bin_no int NULL ) -- helper index CREATE INDEX IX_packages_binno_size ON dbo.packages(bin_no,size) INSERT INTO dbo.packages (size) SELECT (ABS(CHECKSUM(NEWID()))%30) + (ABS(CHECKSUM(NEWID()))%30) + 2 FROM dbo.numbers WHERE n BETWEEN 1 AND 100000

Back to SQL Server main menu. Mail your comments to gertjans@xs4all.nl.