Bin Packing - part 6

09-NOV-2009

Solution 6: Combination matching, most wasteful first

So why do we need a solution 6? Didn't solution 5 already give a perfect result?

Yes it did... for the chosen distribution of packages.

Up to now, the packages had sizes between 2 and 60, based on a pseudo random distribution around 31.

So if your bin packing problem is similar, when you have sizes for which it is also "simple" to find a perfect solution, then solution 5 is for you. Because the solution below will also find a (near) perfect solution for that distribution, it will require close to 3 minutes to run (instead of the 23 seconds of solution 5).

Here we will look at sizes that make it impossible to create a perfect solution. We will look at sizes where the best you can do is get an optimal solution. The sizes used below are between 20 and 68, based on a pseudo random distribution around 49.

Solution 6 shows, that if you have many packages with the same size, and a difficult distribution, then it pays dividends to prioritize the assigment of packages based on the sizes that would result in the most waste when only those packages were left.

The new setup

So let's change the packages. The script below will create new packages, with the "difficult" sizes between 20 and 68.
TRUNCATE TABLE dbo.packages

INSERT INTO dbo.packages (size)
SELECT (ABS(CHECKSUM(NEWID()))%20) + (ABS(CHECKSUM(NEWID()))%30) +20
FROM dbo.numbers
WHERE n BETWEEN 1 AND 100000

Now if I run solutions 1 through 5, then this is the result I get. Because of the random selection, your results can be slightly different. 
solution number_of_bins minimum               percentage                            
-------- -------------- --------------------- ------------------------------------- 
1        56766          43985                 129.057633284074116175969
2        45016          43985                 102.343980902580425144935
3        45016          43985                 102.343980902580425144935
4        45472          43985                 103.380697965215414345799
5        45482          43985                 103.403432988518813231783
There are two things very obvious in these results:
  1. Solution 3 (and 2) does better than solutions 4 and 5.
  2. The best solution doesn't even come close to the perfect ("minimum") solution

So why is solution 3 better than solution 5? Well, solution 5 (and 4) focusses explicitely on finding perfect matches, matches that fill up the bins completely. With these sizes, that is not possible. In the end, too many extra bins need to be added, and under those circumstances, solution 5 (and 4) does not do very well.

The solution below has a different approach. It still uses the method of finding the smallest mix of packages to fill up a bin. What is different, is which packages are used to find the matches of 2 and 3 packages. It is not the biggest remaining packages that is tried first, but the package size that would cause the most waste when only packages of those sizes would be left.

An example to illustrate this. Let's assume that in the unassigned packages, there are many with size 49, and many with size 34. Solution 5 would first try to make a combination with the biggest remaining packages, so it might try to find the combination {49, 31, 20}.

But, if that means that more packages of size 34 remain, then the potential waste is much bigger. A bin of size 100 can only accommodate 2 packages of size 34. A bin with only 2 packages of 34 is much more wasteful than a bin with 2 packages of 49 (32 versus 2 units wasted).

Solution 6 uses the frequency of the package sizes and the potential waste to prioritize the most wasteful packages, such as 34 through 38 (for bins of size 100).

So let's look at the code. I am still using the update_packages_and_bins procedure to process the selection that is prepared in the temporary tables #bins and #packages.
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
I am also using a new procedure. Whenever a combination of 1, 2 or 3 packages is found, this procedure will select the packages of these sizes and call update_packages_and_bins to make the selection permanent.

The procedure also supports a debug flag to print information for debugging purposes. 
CREATE PROCEDURE dbo.assign_packages
(@solution         tinyint
,@debug            bit
,@count            int
,@number_of_values tinyint
,@val1             smallint
,@val2             smallint = null
,@val3             smallint = null) AS
Begin
  If @count > 0
  Begin
    Declare @size smallint
    Set @size=@val1
    If @number_of_values > 1  Set @size=@size+@val2
    If @number_of_values > 2  Set @size=@size+@val3
    
    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
    
    If @number_of_values = 1 AND @debug=1
      select @count,'('+cast(@size as varchar(12))+')',@val1
    
    If @number_of_values >1
    Begin
      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
    End
      
    If @number_of_values = 2 AND @debug=1
      select @count,'('+cast(@size as varchar(12))+')',@val1,@val2
    
    If @number_of_values >2
    Begin
      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
    End
      
    If @number_of_values = 3 AND @debug=1
      select @count,'('+cast(@size as varchar(12))+')',@val1,@val2,@val3
  End
End
And a helper procedure that is only used for debugging purposes.
CREATE PROCEDURE dbo.current_state_of_affairs
(@solution tinyint
,@debug    bit ) AS
Begin
  If @debug=1
  Begin
    SELECT space_left,count(*)
    FROM  dbo.bins
    WHERE solution=@solution
    GROUP BY space_left
    ORDER BY space_left
    
    SELECT size,count(*)
    FROM  dbo.packages
    WHERE bin_no IS NULL
    GROUP BY size
    ORDER BY size DESC
  End
End
Below is the helper procedure that determines (and refreshes) the ranking as described before.
CREATE PROCEDURE dbo.update_ranking
(@bin_size smallint) AS
Begin
  -- Calculate the packages that would result in the most waste
  -- when not combined with packages of different sizes.
  -- (@bin_size % size) is the waste for that size.
  -- It is weighted because the COUNT(*) is taken into account
  TRUNCATE TABLE #ranking
  
  INSERT INTO #ranking
  SELECT size, (COUNT(*)/(@bin_size/size))*(@bin_size%size)
  FROM dbo.packages
  WHERE bin_no IS NULL
  GROUP BY size
  HAVING COUNT(*) >= (@bin_size/size)
End
Below is the helper procedure that counts how many combinations of 2 or 3 sizes are available
CREATE PROCEDURE dbo.count_packages
(@number_of_values tinyint
,@val1             smallint
,@val2             smallint = null
,@val3             smallint = null )AS
Begin
  Declare @count int
  
  If @number_of_values = 1
  Begin
    Set @count = (
      SELECT COUNT(*)
      FROM dbo.packages
      WHERE size = @val1
      AND   bin_no IS NULL )
  End

  If @number_of_values = 2
  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 )
  End
  
  If @number_of_values = 3
  Begin
    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 AND @val2 <> @val3
      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 )
    Else
      SELECT 'Sorry, dbo.count_packages doesn''t support this combination (yet)'
  End
  
  Return @count
End
Here is the main code. Even with the helper procedures, be prepared for very, very much code...
-- Solution 6
UPDATE dbo.packages
SET bin_no = NULL

DELETE FROM dbo.bins
WHERE solution=6

Declare @debug bit
Set @debug=1

Declare @loop             bit
Declare @iteration        int
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
Declare @val1             smallint
Declare @val2             smallint
Declare @val3             smallint

Set @solution = 6
Set @bin_size = 100

-- Calculate minimal number of bins
-- Either determines by total size
Set @min_bins = (
  SELECT CEILING(SUM(size)*1.0/@bin_size)
  FROM dbo.packages )

-- Or the number of packages that cover more than half 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) )

If @extra_bins > @min_bins
Begin
  If @debug=1  select @min_bins as min_bins,@extra_bins as correction
  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 #ranking    (size smallint, weight int, constraint pk primary key (weight,size))

SET NOCOUNT ON
-- Check for packages > @bin_size/2
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 )
  
  EXEC @count = dbo.count_packages 1,@size
  
  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
  If @debug=1  select @count,'('+cast(@size as varchar(12))+')',@size
End

-- Check for packages = @bin_size/2
If EXISTS (
  SELECT *
  FROM dbo.packages
  WHERE bin_no IS NULL
  AND   size = (@bin_size/2) )
Begin
  Set @size=@bin_size/2
  EXEC @count = dbo.count_packages 2,@size,@size
  
  EXEC dbo.assign_packages @solution,@debug,@count,2,@size,@size
End

-- global loop
Set @iteration=0
While EXISTS (
  SELECT *
  FROM dbo.packages
  WHERE bin_no IS NULL )
Begin
  Set @iteration=@iteration+1
  If @debug=1  select @iteration as Iteration
  
  -- fill up, combi=1
  Set @size = 0
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL ) AND @size IS NOT NULL
  Begin
    Set @size = (
      SELECT MIN(space_left)
      FROM dbo.bins
      WHERE solution=@solution
      AND   space_left>@size
      AND   space_left<@bin_size/2 )
    
    If @size IS NOT NULL
    Begin
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left = @size )
      
      EXEC @count = dbo.count_packages 1,@size
      If @count > @space_count
        Set @count = @space_count
      
      EXEC dbo.assign_packages @solution,@debug,@count,1,@size
    End
  End
  
  EXEC dbo.current_state_of_affairs @solution,@debug
  
  -- combi=2, #ranking=2
  EXEC dbo.update_ranking @bin_size
  
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL )
  AND EXISTS (
    SELECT *
    FROM #ranking )
  Begin
    Set @size = (
      SELECT TOP 1 size
      FROM #ranking
      ORDER BY weight DESC, size DESC )
    
    Set @space_count = (
      SELECT COUNT(*)
      FROM dbo.bins
      WHERE solution = @solution
      AND   space_left = 2*@size )
    If @space_count>0
    Begin
      EXEC @count = dbo.count_packages 2,@size,@size
      
      If @count > @space_count
        Set @count = @space_count
      
      If @count > 0
      Begin
        EXEC dbo.assign_packages @solution,@debug,@count,2,@size,@size
        EXEC dbo.update_ranking @bin_size
      End
    End
    Else
    Begin
      DELETE FROM #ranking
      WHERE size=@size
      
      Set @val2=NULL
      Set @val1=@size
      Set @val2=(
        SELECT TOP 1 size
        FROM dbo.bins
        JOIN #ranking
          ON size+@size = space_left
        WHERE solution = @solution
        ORDER BY weight DESC )
      
      If @val2 IS NOT NULL
      Begin
        EXEC @count=dbo.count_packages 2,@val1,@val2
        
        Set @space_count = (
          SELECT COUNT(*)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left = @val1+@val2 )
        
        If @space_count < @count
          Set @count=@space_count
        
        If @count > 0
        Begin
          EXEC dbo.assign_packages @solution,@debug,@count,2,@val1,@val2
          EXEC dbo.update_ranking @bin_size
        End
      End
    End
  End
  
  -- combi=2, #ranking=0
  EXEC dbo.update_ranking @bin_size
  
  Set @size=@bin_size
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL ) AND @size>0
  Begin
    Set @val1 = (
      SELECT MAX(size)
      FROM dbo.packages P1
      WHERE bin_no IS NULL
      AND size < @size
      AND NOT EXISTS (
        SELECT *
        FROM #ranking R1
        WHERE R1.size=P1.size ) )
    Set @size=@val1
    
    Set @val2=NULL
    Set @val2=(
      SELECT TOP 1 size
      FROM dbo.bins
      JOIN dbo.packages P1
        ON size+@size = space_left
      WHERE solution = @solution
      AND   P1.bin_no IS NULL
      ORDER BY size DESC )
    
    If @val2 IS NOT NULL
    Begin
      EXEC @count=dbo.count_packages 2,@val1,@val2
      
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left = @val1+@val2 )
        
      If @space_count < @count
        Set @count=@space_count
      
      If @count > 0
        EXEC dbo.assign_packages @solution,@debug,@count,2,@val1,@val2
    End
  End
  
  -- combi=3, #ranking=3
  EXEC dbo.update_ranking @bin_size
  
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL )
  AND EXISTS (
    SELECT *
    FROM #ranking )
  Begin
    Set @size = (
      SELECT TOP 1 size
      FROM #ranking
      ORDER BY weight DESC, size DESC )
    
    Set @space_count = (
      SELECT COUNT(*)
      FROM dbo.bins
      WHERE solution = @solution
      AND   space_left = 3*@size )
    If @space_count>0
    Begin
      EXEC @count = dbo.count_packages 3,@size,@size,@size
      
      If @count > @space_count
        Set @count = @space_count
      
      If @count > 0
      Begin
        EXEC dbo.assign_packages @solution,@debug,@count,3,@size,@size,@size
        EXEC dbo.update_ranking @bin_size
      End
    End
    Else
    Begin
      DELETE FROM #ranking
      WHERE size=@size
      
      Set @val3=(
        SELECT MIN(size)
        FROM #ranking )
      Set @val2=NULL
      Set @val1=@size
      Set @val2=(
        SELECT TOP 1 size
        FROM dbo.bins
        JOIN #ranking
          ON size+@val1 + @val3 <= space_left
        WHERE solution = @solution
        ORDER BY weight DESC )
      
      If @val2 IS NOT NULL
        Set @val3=(
          SELECT TOP 1 size
          FROM dbo.bins
          JOIN #ranking
            ON size+@val1 + @val2 = space_left
          WHERE solution = @solution
          AND   size <> @val2
          ORDER BY weight DESC )
      
      If @val2 IS NOT NULL AND @val3 IS NOT NULL
      Begin
        EXEC @count=dbo.count_packages 3,@val1,@val2,@val3
        
        Set @space_count = (
          SELECT COUNT(*)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left = @val1+@val2+@val3 )
        
        If @space_count < @count
          Set @count=@space_count
        
        If @count > 0
        Begin
          EXEC dbo.assign_packages @solution,@debug,@count,3,@val1,@val2,@val3
          EXEC dbo.update_ranking @bin_size
        End
      End
    End
  End
  
  -- combi=3, #ranking=2
  EXEC dbo.update_ranking @bin_size
  
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL )
  AND EXISTS (
    SELECT *
    FROM #ranking )
  Begin
    Set @size = (
      SELECT TOP 1 size
      FROM #ranking
      ORDER BY weight DESC, size DESC )
    
    DELETE FROM #ranking
    WHERE size=@size
    
    Set @val3=(
      SELECT MIN(size)
      FROM  dbo.packages
      WHERE bin_no IS NULL )
    
    Set @val2=NULL
    Set @val1=@size
    Set @val2=(
      SELECT TOP 1 size
      FROM dbo.bins
      JOIN #ranking
        ON size+@val1 + @val3 <= space_left
      WHERE solution = @solution
      ORDER BY weight DESC )
    
    If @val2 IS NOT NULL
      Set @val3=(
        SELECT TOP 1 size
        FROM dbo.bins
        JOIN dbo.packages P1
          ON size+@val1+@val2 = space_left
        WHERE solution = @solution
        AND   P1.bin_no IS NULL
        AND   size NOT IN (@val1,@val2)
        ORDER BY size DESC )
    
    If @val2 IS NOT NULL AND @val3 IS NOT NULL
    Begin
      EXEC @count=dbo.count_packages 3,@val1,@val2,@val3
        
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left = @val1+@val2+@val3 )
        
      If @space_count < @count
        Set @count=@space_count
      
      If @count > 0
      Begin
        EXEC dbo.assign_packages @solution,@debug,@count,3,@val1,@val2,@val3
        EXEC dbo.update_ranking @bin_size
      End
    End
  End
  
  -- combi=3, #ranking=1
  EXEC dbo.update_ranking @bin_size
  
  While EXISTS (
    SELECT *
    FROM dbo.packages
    WHERE bin_no IS NULL )
  AND EXISTS (
    SELECT *
    FROM #ranking )
  Begin
    Set @size=(
      SELECT MAX(space_left)
      FROM dbo.bins
      WHERE solution = @solution )
    
    Set @val3=(
      SELECT MIN(size)
      FROM  dbo.packages
      WHERE bin_no IS NULL )
    
    DELETE FROM #ranking
    WHERE size > (@size - @val3 - @val3)
    
    Set @val1=NULL
    Set @val1 = (
      SELECT TOP 1 size
      FROM #ranking
      ORDER BY weight DESC, size DESC )
    
    DELETE FROM #ranking
    WHERE size=@val1
    
    Set @val2=NULL
    Set @val2=(
      SELECT MAX(size)
      FROM dbo.packages
      WHERE bin_no IS NULL
      AND   size <= @size-@val1-@val3
      AND   size <> @val1 )
   
    If @val2 IS NOT NULL
      Set @val3=(
        SELECT TOP 1 size
        FROM dbo.bins
        JOIN dbo.packages P1
          ON size+@val1+@val2 = space_left
        WHERE solution = @solution
        AND   P1.bin_no IS NULL
        AND   size NOT IN (@val1,@val2)
        ORDER BY size DESC )
    
    If @val2 IS NOT NULL AND @val3 IS NOT NULL
    Begin
      EXEC @count=dbo.count_packages 3,@val1,@val2,@val3
      
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left = @val1+@val2+@val3 )
      
      If @space_count < @count
        Set @count=@space_count
     
      If @count > 0
      Begin
        EXEC dbo.assign_packages @solution,@debug,@count,3,@val1,@val2,@val3
        EXEC dbo.update_ranking @bin_size
      End
    End
  End
  
  -- fillers
  Set @loop=1
  While @loop=1
  Begin
    If @debug=1  print 'fillers'
    Set @loop=0
    
    Set @val3=(
      SELECT MIN(size)
      FROM  dbo.packages
      WHERE bin_no IS NULL )
    
    If @val3 IS NOT NULL
    Begin
      -- No combination of values can fit the space
      Set @space_count = (
        SELECT COUNT(*)
        FROM dbo.bins
        WHERE solution = @solution
        AND   space_left < @val3+@val3
        AND   space_left >= @val3 )
      
      If @space_count > 0
      Begin
        Set @size=(
          SELECT MIN(space_left)
          FROM dbo.bins
          WHERE solution = @solution
          AND   space_left < @val3+@val3
          AND   space_left >= @val3 )
        
        If @size IS NOT NULL
        Begin
          Set @val1=(
            SELECT MAX(size)
            FROM dbo.packages
            WHERE bin_no IS NULL
            AND   size <= @size )
          
          EXEC @count=dbo.count_packages 1,@val1
          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 < @val3+@val3
            AND   space_left >= @val3
            
            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
            If @debug=1  select @count,'('+cast(@size as varchar(12))+')',@val1
            
            Set @loop=1
          End
        End
      End
    End
  End


  -- no combi=4, so simply assign the biggest remaining package
  Set @size=(
    SELECT MAX(size)
    FROM  dbo.packages
    WHERE bin_no IS NULL )
  
  Set @space_count = (
    SELECT COUNT(*)
    FROM dbo.bins
    WHERE solution = @solution
    AND   space_left >= @size )
  
  If @space_count > 0
  Begin
    If @debug=1  print 'no combi=4'
    
    Set @val1=@size
    EXEC @count=dbo.count_packages 1,@val1
    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
      If @debug=1  select @count,'('+cast(@size as varchar(12))+')',@val1
    End
  End
  Else
  Begin
    If EXISTS (
      SELECT *
      FROM dbo.packages
      WHERE bin_no IS NULL )
    Begin
      -- The biggest package doesn't fit, so extra bins are required
      If @debug=1  print 'need to add bins'
      EXEC dbo.current_state_of_affairs @solution,@debug

      Set @count=CEILING((
        SELECT COUNT(*)
        FROM dbo.packages
        WHERE bin_no IS NULL
        AND   size=@size )*1.0 / (@bin_size / @size) )
      
      Set @extra_bins = CEILING((
          SELECT SUM(size)
          FROM dbo.packages
          WHERE bin_no IS NULL ) * 1.0 / @bin_size)
  
      If @debug=1  select @count,@extra_bins as extra_bins
      
      If @count > @extra_bins
        Set @extra_bins=@count
      
      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
    End
  End
End

If @debug=1  select getdate(),@iteration as Iteration

SET NOCOUNT OFF

DROP TABLE #ranking
DROP TABLE #packages
DROP TABLE #bins
Let's get the results
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        56766          43985                 129.057633284074116175969
2        45016          43985                 102.343980902580425144935
3        45016          43985                 102.343980902580425144935
4        45472          43985                 103.380697965215414345799
5        45482          43985                 103.403432988518813231783
6        44299          43985                 100.713879731726725019893
Fortunately, this result is much better than solution 3. The code ran for 29 seconds.

Is this the optimal solution? Or is there a solution with 44298 packages out there?
If you find a better solution, using some kind of formula, then I am very interested, and you should e-mail me!

For me, the search continues for an even better solution...

Part 5 - Solution 5 | Part 7 - Brute Force discovery


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