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.
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.
The solutions
This series of articles shows different approaches to the bin packing problem, in search of
the "best" solution:
The setup
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
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