Gert-Jan's SQL Server solutions - bin packing

15-OCT-2009

Solution 4: Combination matching, fewest first

So now it finally gets interesting. What if the cost of wasted bins is much higher than the cost of computing a better solution? In other words, if there is sufficient computing time, how can we improve the results better than the 0.25% waste that Solution 2 and Solution 3 achieves?

There is one area. The previous solutions have a specific problem. Typically, situations like this cause waste: Assume there is a bin with 8 space left. You are processing a package with size 6, and decide to add it to this bin, leaving a space of 2. Next comes a package of size 4, and next another package of size 4. Both packages of size 4 will not fit in space of 2, which means that the next bin will be filled up earlier.

Here is another example. In our example, each package has a size between 2 and 30. There is no package with size 1. So any bin with 1 free space has wasted this space, because no package will fit in there.

The solution is to match combinations of packages.

Bin Packing is an NP-complete problem, which means it is not practical to try to figure out all potential solutions. For that, no amount of time would suffice.

The method used below, is to try to fill up a bin with as few packages as possible. When few packages are used, then the average package size is big. So any remaining "problematic" packages will be small in size, resulting in fewer waste.

So what "depth" of combinations should be evaluated? Is a combination of 2 sufficient? If a combination of 10 sufficient? Obviously the number of potential combination for the same total size grows exponentially with the "depth". There are also definitely deminishing returns.

So in the code below, the matches are limited to a maximum of only 2 values. If there is no combination of 2 values to fill a bin, then packages are added to the bin until there is a combination of (at most) 2 values to fill up the bin.

The code uses a stored procedure to implement the required recursion.

The first part is a helper stored procedure. It will persist the selected bins and packages as listed in the temporary tables #bins and #packages.

-- Solution 4
CREATE PROCEDURE dbo.update_packages_and_bins
(@solution tinyint
,@size     smallint) AS
Begin
  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

The second part is a very important stored procedure. It tries to match with one value or a combination of two values. It is the heart of this bin packing solution.

CREATE PROCEDURE dbo.find_match
(@solution         tinyint
,@number_of_values tinyint
,@size             smallint
,@bin_size         smallint ) AS
Begin
  Declare @count       int
  Declare @space_count int
  Declare @max_val     smallint
  Declare @val1        smallint
  Declare @val2        smallint
  
  Set @space_count = (
    SELECT COUNT(*)
    FROM dbo.bins
    WHERE solution = @solution
    AND   space_left = @size )
  
  If @space_count = 0
    Return
  
  If @number_of_values = 1
  Begin
    Set @count = (
      SELECT COUNT(*)
      FROM dbo.packages
      WHERE size = @size
      AND   bin_no IS NULL )
    
    If @count > @space_count
      Set @count = @space_count
    
    If @count > 0
    Begin
      TRUNCATE TABLE #bins
      INSERT INTO #bins (bno)
      SELECT TOP (@count) bin_no
      FROM dbo.bins
      WHERE solution = @solution
      AND   space_left = @size
      
      TRUNCATE TABLE #packages
      INSERT INTO #packages (pno)
      SELECT TOP (@count) package_no
      FROM dbo.packages
      WHERE bin_no IS NULL
      AND   size = @size
      
      EXEC dbo.update_packages_and_bins @solution,@size
    End
  End
  
  If @number_of_values = 2
  Begin
    Set @val1=@size/2;
    Set @val2=@size-@val1;
    Set @max_val=(
      SELECT MAX(size)
      FROM dbo.packages
      WHERE bin_no IS NULL )
    
    While @val1>0 AND @val2 <= @max_val
    Begin
      If @val1=@val2
        Set @count=(
          SELECT COUNT(*)/2
          FROM dbo.packages
          WHERE size = @val1
          AND   bin_no IS NULL )
      Else
        Set @count=(
          SELECT MIN(cnt) FROM (
            SELECT COUNT(*) AS cnt
            FROM dbo.packages
            WHERE size = @val1
            AND   bin_no IS NULL
            
            UNION ALL
            
            SELECT COUNT(*)
            FROM dbo.packages
            WHERE size = @val2
            AND   bin_no IS NULL
          ) AS T )
      
      If @space_count < @count
        Set @count=@space_count
      
      If @count > 0
      Begin
        TRUNCATE TABLE #bins
        INSERT INTO #bins (bno)
        SELECT TOP (@count) bin_no
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left = @size
        
        TRUNCATE TABLE #packages
        INSERT INTO #packages (pno)
        SELECT TOP (@count) package_no
        FROM dbo.packages
        WHERE bin_no IS NULL
        AND   size = @val1
        
        EXEC dbo.update_packages_and_bins @solution,@val1
        
        TRUNCATE TABLE #packages
        INSERT INTO #packages (pno)
        SELECT TOP (@count) package_no
        FROM dbo.packages
        WHERE bin_no IS NULL
        AND   size = @val2
        
        EXEC dbo.update_packages_and_bins @solution,@val2
        
        Set @space_count = (
          SELECT COUNT(*)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left = @size )
        
        If @space_count = 0
          BREAK
      End
      
      Set @val1=@val1-1;
      Set @val2=@size-@val1;
      
      If NOT EXISTS (
        SELECT *
        FROM dbo.packages
        WHERE bin_no IS NULL
        AND   size=@val1 )
      Begin
        Set @val1 = (
          SELECT MAX(size)
          FROM dbo.packages
          WHERE bin_no IS NULL
          AND   size < @val1 )
        Set @val2=@size-@val1;
      End
    End
  End
End

And finally, the setup and the loopings.

UPDATE dbo.packages
SET bin_no = NULL

DELETE FROM dbo.bins
WHERE solution=4

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

Set @solution = 4
Set @bin_size = 100
Set @min_bins = (
  SELECT CEILING(SUM(size)*1.0/@bin_size)
  FROM dbo.packages )

INSERT INTO dbo.bins (solution, bin_no, space_left)
SELECT @solution, n, @bin_size
FROM dbo.numbers
WHERE n BETWEEN 1 AND @min_bins

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 @number_of_values = 1
  
  While @number_of_values < 3
  Begin
    Set @size = (
      SELECT MIN(space_left)
      FROM dbo.bins
      WHERE solution=@solution
      AND   space_left>0 )
    
    While @size > 0
    Begin
      EXEC dbo.find_match @solution,@number_of_values,@size,@bin_size
      
      Set @size = (
        SELECT MIN(space_left)
        FROM dbo.bins
        WHERE solution=@solution
        AND   space_left>@size )
    End
    Set @number_of_values = @number_of_values + 1
  End
  
  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
  
  EXEC dbo.update_packages_and_bins @solution,@size
End
SET NOCOUNT OFF

DROP TABLE #packages
DROP TABLE #bins

Now on my system, this solution is finished in 25, so it is faster than solution 3.

So how much better is the result?

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
4        31013          31011                 100.006449324433265615426

Wow! Near perfect! Only 2 bins more than a perfect fit.

Bin Packing - part 4

Solution 4: Combination matching, fewest first