Bin Packing - the basics

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

Part 1 - Solution 1


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