Bin Packing - part 5

08-NOV-2009

Solution 5: Combination matching, fewest first, optimized

This solution builds upon solution 4. As a final step, let's support combinations of 3 values.

It is very important to be smart about which combinations to try. You want to avoid the situation where you combine 2 large packages with 1 small packages, because then you will end up with a lot of medium sized packages and not enough small packages.

So when it comes to a combination of 3 values, the solution below will always try to combine 1 large package with 2 medium sized packages, or try 3 medium sized packages

We will replace the find_match stored procedure with one that will support combinations up to 3 values.

If you looked at the earlier version, you have seen how combinations are processed. The new part about this version is the formula to determine the combination of 3 values that is then tried.

It also includes an optimization. Once find_match has detemined that it has no match for a certain size (anymore), it is added to the #examined table, and never retried again. 
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 @min_val     smallint
  Declare @max_val     smallint
  Declare @val1        smallint
  Declare @val2        smallint
  Declare @val3        smallint
  Declare @continue    tinyint
  
  -- only when useful
  If EXISTS (
    SELECT *
    FROM #examined
    WHERE space_left=@size )  RETURN
  
  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
  
  If @number_of_values = 3
  Begin
    Set @min_val=(
      SELECT MIN(size)
      FROM dbo.packages
      WHERE bin_no IS NULL )
    
    Set @max_val=(
      SELECT MAX(size)
      FROM dbo.packages
      WHERE bin_no IS NULL )
    
    Set @val1 = @max_val
    Set @val2 = CEILING((@size - @val1)/2.0)
    While @val1 > 0
    Begin
      Set @continue=0
      While @continue=0
      Begin
        Set @val2 = @val2 - 1
        Set @val3 = @size - @val1 - @val2
        
        If @val1 > @max_val
        Begin
          Set @val1 = @max_val
          Set @val2 = CEILING((@size - @val1)/2.0)
        End
        Else If @val2 < (@val1/3)
        Begin
          Set @val1 = @val1 - 1
          Set @val2 = CEILING((@size - @val1)/2.0)
        End
        Else If @val3 > @val1
        Begin
          Set @val1 = @val1 - 1
          Set @val2 = CEILING((@size - @val1)/2.0)
        End
        Else If @val3 BETWEEN @min_val AND @max_val
          Set @continue=1
        
        If @val1 < @min_val
          Set @continue=1
      End
      
      If @val1 < @min_val
        BREAK
      
      If @val1=@val2 AND @val1=@val3
        Set @count=(
          SELECT COUNT(*)/3
          FROM dbo.packages
          WHERE size = @val1
          AND   bin_no IS NULL )
      Else If @val1=@val2 AND @val1<>@val3
        Set @count=(
          SELECT MIN(cnt) FROM (
            SELECT COUNT(*)/2 AS cnt
            FROM dbo.packages
            WHERE size=@val1
            AND   bin_no IS NULL
            UNION ALL
            SELECT COUNT(*)
            FROM dbo.packages
            WHERE size=@val3
            AND   bin_no IS NULL ) AS T )
      Else If @val1=@val3 AND @val2<>@val3
        Set @count=(
          SELECT MIN(cnt) FROM (
            SELECT COUNT(*)/2 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 )
      Else If @val2=@val3 AND @val1<>@val3
        Set @count=(
          SELECT MIN(cnt) FROM (
            SELECT COUNT(*)/2 AS cnt
            FROM dbo.packages
            WHERE size=@val2
            AND   bin_no IS NULL
            UNION ALL
            SELECT COUNT(*)
            FROM dbo.packages
            WHERE size=@val1
            AND   bin_no IS NULL ) AS T )
      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
            UNION ALL
            SELECT COUNT(*)
            FROM dbo.packages
            WHERE size=@val3
            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
        
        TRUNCATE TABLE #packages
        INSERT INTO #packages (pno)
        SELECT TOP (@count) package_no
        FROM dbo.packages
        WHERE bin_no IS NULL
        AND   size = @val3
        
        EXEC dbo.update_packages_and_bins @solution,@val3
        
        Set @space_count = (
          SELECT COUNT(*)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left = @size )
        
        If @space_count = 0
          BREAK
        
        Set @min_val=(
          SELECT MIN(size)
          FROM dbo.packages
          WHERE bin_no IS NULL )
        
        Set @max_val=(
          SELECT MAX(size)
          FROM dbo.packages
          WHERE bin_no IS NULL )
      End
    End
  End
  
  If @number_of_values = 4
  Begin
    -- never re-examine this size
    INSERT INTO #examined (space_left) VALUES (@size)
  End
End

And finally, the updated "main" program.

There are some additional optimizations in this version, such as the initial calculation of the number of required bins and when extra bins are required, as well as other optimizations.

UPDATE dbo.packages
SET bin_no = NULL

DELETE FROM dbo.bins
WHERE solution=5

Declare @loop             bit
Declare @space_count      int
Declare @count            int
Declare @solution         tinyint
Declare @bin_size         smallint
Declare @size             smallint
Declare @min_size         smallint
Declare @val1             smallint
Declare @min_bins         int
Declare @extra_bins       int
Declare @number_of_values tinyint

Set @solution = 5
Set @bin_size = 100
Set @min_bins = (
  SELECT CEILING(SUM(size)*1.0/@bin_size)
  FROM dbo.packages )
  
-- each package bigger than half the size of the bin requires a bin
Set @extra_bins = (
  SELECT COUNT(*)
  FROM dbo.packages
  WHERE size > (@bin_size/2)
) + (
  SELECT COUNT(*)/2
  FROM dbo.packages
  WHERE size = (@bin_size/2) )

-- whichever is bigger
If @extra_bins > @min_bins
Begin
  Set @min_bins=@extra_bins
End

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)
CREATE TABLE #examined (space_left smallint PRIMARY KEY)

SET NOCOUNT ON
-- Process packages that need their own bin
While EXISTS (
  SELECT *
  FROM dbo.packages
  WHERE bin_no IS NULL
  AND   size > (@bin_size/2) )
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 )
  
  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

While EXISTS (
  SELECT *
  FROM dbo.packages
  WHERE bin_no IS NULL )
Begin
  Set @number_of_values = 1
  
  While @number_of_values < 5
  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
  
  -- fillers. If no combination of values will fit in the space left,
  -- then insert the biggest single value
  Set @loop=1
  While @loop=1
  Begin
    Set @loop=0
    
    Set @min_size=(
      SELECT MIN(size)
      FROM  dbo.packages
      WHERE bin_no IS NULL )
    
    If @min_size IS NOT NULL
    Begin
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left < @min_size+@min_size
        AND   space_left >= @min_size )
      
      If @space_count > 0
      Begin
        Set @size=(
          SELECT MIN(space_left)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left < @min_size+@min_size
          AND   space_left >= @min_size )
        
        If @size IS NOT NULL
        Begin
          Set @val1=(
            SELECT MAX(size)
            FROM dbo.packages
            WHERE bin_no IS NULL
            AND   size <= @size )
          
          Set @count=(
            SELECT COUNT(*) AS cnt
            FROM dbo.packages
            WHERE size = @val1
            AND   bin_no IS NULL )
          
          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 < @min_size+@min_size
            AND   space_left >= @min_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
            
            Set @loop=1
          End
        End
      End
    End
  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)
    
    -- Test if even the smallest remaining package does not fit any bin
    -- If so, then potentially more extra bins are required
    If (
      SELECT MIN(size)
      FROM dbo.packages
      WHERE bin_no IS NULL
    ) > (
      SELECT MAX(space_left)
      FROM dbo.bins
      WHERE solution = @solution )
    Begin
      Set @extra_bins = CEILING((
        SELECT SUM(size)
        FROM dbo.packages
        WHERE bin_no IS NULL ) * 1.0 / @bin_size)
    End
    
    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 #examined
DROP TABLE #packages
DROP TABLE #bins
Although this procedure will test more combinations, it also has some optimizations. Now on my system, this solution is finished in 23 seconds, so it is not slower.

How about 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
5        31011          31011                 100.000000000000000000000
What do you know! PERFECT!

Apparently for this amount of packages (100,000), with this type of distribution (between 2 and 60, bell-curved) this solution seems to be enough to get a perfect or near perfect result.

Part 4 - Solution 4 | Part 6 - Solution 6


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