Gert-Jan's SQL Server solutions - bin packing

15-OCT-2009

Solution 3: Start to Finish, looking back, in groups

Solution 2 was quite good, but too slow. It was slow because of the row by row processing of the cursor. Processing rows in groups should be (much) faster.

Because the following solution processes rows in groups, it might use slightly more bins.

The implementation below uses a set based approach and iteration.

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

DELETE FROM dbo.bins
WHERE solution=3

Declare @solution    tinyint
Declare @bin_size    smallint
Declare @size        smallint
Declare @count       int
Declare @min_bins    int
Declare @space_count int
Declare @extra_bins  int

Set @solution = 3
Set @bin_size = 100
Set @min_bins = 0

CREATE TABLE #bins     (bid int IDENTITY PRIMARY KEY,bno int NOT NULL)
CREATE TABLE #packages (pid int IDENTITY PRIMARY KEY,pno int NOT NULL)

SET NOCOUNT ON
While EXISTS (
  SELECT *
  FROM dbo.packages
  WHERE bin_no IS NULL )
Begin
  Set @size = (
    SELECT MAX(size)
    FROM dbo.packages
    WHERE bin_no IS NULL )
  
  Set @count = (
    SELECT COUNT(*)
    FROM dbo.packages
    WHERE size = @size
    AND   bin_no IS NULL )
  
  Set @space_count = (
    SELECT COUNT(*)
    FROM dbo.bins
    WHERE solution = @solution
    AND   space_left >= @size )
  
  If @space_count = 0
  Begin
    Set @extra_bins = CEILING(@count * @size * 1.0 / @bin_size)
    
    INSERT INTO dbo.bins (solution, bin_no, space_left)
    SELECT @solution, n, @bin_size
    FROM dbo.numbers
    WHERE n BETWEEN @min_bins+1 AND @min_bins+@extra_bins
    
    Set @min_bins = @min_bins + @extra_bins
    Set @space_count = @extra_bins
  End
  
  If @space_count < @count
    Set @count = @space_count
  
  TRUNCATE TABLE #bins
  INSERT INTO #bins (bno)
  SELECT TOP (@count) bin_no
  FROM dbo.bins
  WHERE solution = @solution
  AND   space_left >= @size
  ORDER BY space_left ASC
  
  TRUNCATE TABLE #packages
  INSERT INTO #packages (pno)
  SELECT TOP (@count) package_no
  FROM dbo.packages
  WHERE bin_no IS NULL
  AND   size = @size
  
  UPDATE dbo.packages
  SET bin_no = (
    SELECT bno
    FROM #bins
    JOIN #packages on pid=bid
    WHERE pno=package_no )
  WHERE EXISTS (
    SELECT *
    FROM #packages
    WHERE pno = package_no )
  
  UPDATE dbo.bins
  SET space_left = space_left - @size
  WHERE solution = @solution
  AND   EXISTS (
    SELECT *
    FROM #bins
    WHERE bno = bin_no )
End
SET NOCOUNT OFF

DROP TABLE #packages
DROP TABLE #bins

Now on my system, this solution is finished in 47 seconds instead of the 16 minutes of solution 2.

Let's see how much poorer the result is.

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

Now that's pleasant! Solution 3 performs just as good as solution 2, it simply is 20 times faster.

Bin Packing - part 3

Solution 3: Start to Finish, looking back, in groups