Gert-Jan's SQL Server solutions - bin packing

15-OCT-2009

Solution 2: Start to Finish, but looking back

The same basic solution, but optimized, is to look back whenever the current package does not fit the current bin. If there is a bin that still has room for it, then no new bin has to be created.

Also, this solution will sort the packages in descending order. This avoids the problem of large packages near the end that cannot be "filled up" with smaller packages.

So this solution should give a considerably better fit, resulting is fewer bins.

The implementation below uses an iterative approach using a cursor.

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

DELETE FROM dbo.bins
WHERE solution=2

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

Set @solution = 2
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 size DESC

OPEN c

SET NOCOUNT ON

FETCH NEXT FROM c INTO @package_no, @size

While @@FETCH_STATUS = 0
Begin
  If @filled + @size <= @bin_size
  Begin
    UPDATE dbo.packages
    SET bin_no = @bin_no
    WHERE package_no = @package_no
    
    Set @filled = @filled + @size
  End
  Else
  Begin
    Set @old_bin_no=NULL
    Set @old_bin_no=(
      SELECT TOP 1 bin_no
      FROM dbo.bins
      WHERE solution = @solution
      AND   space_left >= @size
      ORDER BY space_left, bin_no )
    
    If @old_bin_no IS NOT NULL
    Begin
      UPDATE dbo.bins
      SET space_left = space_left - @size
      WHERE solution = @solution
      AND   bin_no = @old_bin_no
      
      UPDATE dbo.packages
      SET bin_no = @old_bin_no
      WHERE package_no = @package_no
    End
    Else
    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 = @size
      
      UPDATE dbo.packages
      SET bin_no = @bin_no
      WHERE package_no = @package_no
    End
  End
  
  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

Now we can expect this approach to run slower than solution 1. And it does. Where solution 1 ran for over 14 minutes on my system, solution 2 takes over 16 minutes.

So let's see if it was worth the wait.

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
2        31090          31011                                   100.254748315113991809357

which indicates that only 0.25% more bins are used when compared to a perfect assignment.

Bin Packing - part 2

Solution 2: Start to Finish, but looking back