Gert-Jan's SQL Server solutions - bin packing

08-NOV-2009, last improvement 19-MAY-2013

Solution 1: Start to Finish

The first approach is the "I don't want to think about it" approach. You start with a bin, and add packages until you find a package that doesn't fit anymore. You then add another bin, start filling that, and never look back.

The implementation below uses an iterative approach using a cursor.

-- Solution 1
UPDATE dbo.packages
SET bin_no = NULL

DELETE FROM dbo.bins
WHERE solution=1

Declare @solution   tinyint
Declare @bin_size   smallint
Declare @size       smallint
Declare @filled     smallint
Declare @package_no int
Declare @bin_no     int

Set @solution = 1
Set @bin_size = 100
Set @filled = 0
Set @bin_no = 1

DECLARE c CURSOR FAST_FORWARD FOR
SELECT package_no, size
FROM dbo.packages
ORDER BY package_no

OPEN c

SET NOCOUNT ON

FETCH NEXT FROM c INTO @package_no, @size

While @@FETCH_STATUS = 0
Begin
  If @filled + @size > @bin_size
  Begin
    INSERT INTO dbo.bins (solution, bin_no, space_left)
    VALUES (@solution, @bin_no, @bin_size - @filled)
    
    Set @bin_no = @bin_no + 1
    Set @filled = 0
  End
  
  UPDATE dbo.packages
  SET bin_no = @bin_no
  WHERE package_no = @package_no
  
  Set @filled = @filled + @size
  
  FETCH NEXT FROM c INTO @package_no, @size
End

IF @filled > 0
  INSERT INTO dbo.bins (solution, bin_no, space_left)
  VALUES (@solution, @bin_no, @bin_size - @filled)

SET NOCOUNT OFF

CLOSE c
DEALLOCATE c

When you run this example, then be prepared for a 14 minute break, because the iterative approach will process the 100,000 packages one by one, which is very slow.

Not only is it slow, but the result is poor as well. Let's check the efficiency with the script below

Declare @bin_size smallint
Set @bin_size=100

SELECT solution
,      COUNT(bin_no) AS number_of_bins
,      CEILING(SUM(@bin_size-space_left)*1.0/@bin_size) AS minimum
,      COUNT(bin_no) * 100.0 / CEILING(SUM(@bin_size-space_left)*1.0/@bin_size)  AS percentage
FROM dbo.bins
GROUP BY solution
ORDER BY solution

The results will depend on the sample data (the packages). Your results could look something like this:

solution number_of_bins minimum               percentage                            
-------- -------------- --------------------- ------------------------------------- 
1        37436          31011                 120.718454741865789558543

which indicates that more than 20% more bins are used when compared to a perfect assignment.

Bin Packing - part 1

Solution 1: Start to Finish