Created: 15-OCT-2009. Last Modified: 31-DEC-2011
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.
Many packages in many sizes.
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.
This series of articles shows different approaches to the bin packing problem, in search of
the "best" solution:
The example used here resembles the cable cutting problem. The example is, that there are many
packages of different sizes, that have to be assigned to bins that have a fixed size.
The goal is to minimize the number of bins. Or - to put it differently - to minimize waste.
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)
Below is the definition of the packages table, and a script to populate it with 100,000 entries.
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
While 100000 > @i
INSERT INTO dbo.numbers
SELECT n+@i FROM dbo.numbers
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
WHERE n BETWEEN 1 AND 100000