Bin Packing - part 8

19-MAY-2013

Solution 8: Brute Force discovery for many packages

The previous solution is fine for a small number of packages. For a bigger number of packages, if you use the previous solution, your database will run out of space.

The solution to solve that, is to switch strategy once the number of potential solutions grows too big. In the code (below) the limit is set to 100,000 potential solutions. Once the search space grows bigger, it will "save" the current state of affairs in a "checkpoint", and continue searching with only the "last" 75,000 rows (on average).

The two main advantages of this approach are:
  1. The space requirements are much much lower. The space required no longer grows exponentially
  2. If there are multiple solutions, then on average, one such solution will be found earlier


There are a few more optimizations in the code. They will be discussed with the relevant piece of code.

Example

The example for this code are 50 packages that are to be placed in bins of size 100. The best solution so far needs 19 bins, but there could be a solution with 18 bins, so this brute force strategy is a good way to find out. Since there actually is a solution for 18 bins, the code will finish between 30 and 60 minutes. If all potential solutions would have to be investigated, it could have been hours, days, weeks, months or even more.

package_no  size
----------- ------
1           51
2           23
3           57
4           40
5           60
6           36
7           36
8           46
9           37
10          46
11          47
12          12
13          45
14          42
15          38
16          33
17          36
18          51
19          51
20          25
21          29
22          30
23          26
24          27
25          52
26          23
27          36
28          29
29          19
30          19
31          39
32          21
33          51
34          20
35          10
36          15
37          43
38          36
39          37
40          50
41          30
42          57
43          29
44          47
45          38
46          32
47          30
48          40
49          35
50          14

Code

Let's move on to the code.

Notice that all tables that will hold a lot of rows only have a clustered index. It would be slower if more indexes were added.

The "checkpoints" table will keep track of the "branches" that need to be investigated. These branches are made every time the number of potential solutions grows beyond 100,000.

-- placeholder per potential solution
CREATE TABLE dbo.solutions
(solution     int           IDENTITY PRIMARY KEY CLUSTERED
,processed    tinyint       NOT NULL
,total_waste  smallint      NOT NULL
,more_waste   smallint          NULL
,derived_from int               NULL
,bin_no       smallint          NULL
,space_left   int               NULL
,bins         varchar(4000)     NULL
)

-- help table with selected potential solutions
CREATE TABLE dbo.positions
(solution    int           NOT NULL
,bin_no      smallint      NOT NULL
,space_left  smallint          NULL
,more_waste  smallint          NULL
,bins        varchar(4000)     NULL
,CONSTRAINT PK_positions PRIMARY KEY CLUSTERED (solution, bin_no)
)

CREATE TABLE dbo.checkpoints
(solution   int      NOT NULL
,package_no smallint NOT NULL
,size       smallint NOT NULL
,bin_no     smallint     NULL
,CONSTRAINT PK_checkpoints PRIMARY KEY CLUSTERED (solution,package_no)
)

CREATE TABLE dbo.positions2
(solution    int      NOT NULL
,package_no  smallint NOT NULL
,CONSTRAINT PK_positions2 PRIMARY KEY CLUSTERED (solution, package_no)
)

-- help table with duplicate potential solutions
CREATE TABLE dbo.duplicates
(solution int          NOT NULL
,packages varchar(900) NOT NULL
)
CREATE CLUSTERED INDEX CL_duplicates ON dbo.duplicates(packages)

-- packages and their placement, per potential solution
CREATE TABLE dbo.tries_P
(solution       int      NOT NULL
,package_no     smallint NOT NULL
,size           smallint NOT NULL
,bin_no         smallint     NULL
,CONSTRAINT PK_tries_P PRIMARY KEY CLUSTERED(solution,package_no)
)

-- bins, per potential solution
CREATE TABLE dbo.tries_B
(solution     int      NOT NULL
,bin_no       smallint NOT NULL
,space_left   smallint NOT NULL
,fill_up      int          NULL
,derived_from int          NULL
,changed      bit          NULL
,CONSTRAINT PK_tries_B PRIMARY KEY CLUSTERED (solution,bin_no)
)

-- helper table
CREATE TABLE dbo.numbers (n int PRIMARY KEY)

INSERT INTO dbo.numbers VALUES (1)
Declare @i int
Set @i=1
While 100000 > @i
Begin
  INSERT INTO dbo.numbers
  SELECT n+@i FROM dbo.numbers
  
  Set @i=@i*2
End

-- source table with the packages
CREATE TABLE dbo.packages
(package_no smallint IDENTITY PRIMARY KEY
,size       smallint NOT NULL
,bin_no     smallint     NULL
)
CREATE INDEX IX_packages_binno_size ON dbo.packages(bin_no,size)

-- the 50 packages
insert into dbo.packages (size) values (51)
insert into dbo.packages (size) values (23)
insert into dbo.packages (size) values (57)
insert into dbo.packages (size) values (40)
insert into dbo.packages (size) values (60)
insert into dbo.packages (size) values (36)
insert into dbo.packages (size) values (36)
insert into dbo.packages (size) values (46)
insert into dbo.packages (size) values (37)
insert into dbo.packages (size) values (46)
insert into dbo.packages (size) values (47)
insert into dbo.packages (size) values (12)
insert into dbo.packages (size) values (45)
insert into dbo.packages (size) values (42)
insert into dbo.packages (size) values (38)
insert into dbo.packages (size) values (33)
insert into dbo.packages (size) values (36)
insert into dbo.packages (size) values (51)
insert into dbo.packages (size) values (51)
insert into dbo.packages (size) values (25)
insert into dbo.packages (size) values (29)
insert into dbo.packages (size) values (30)
insert into dbo.packages (size) values (26)
insert into dbo.packages (size) values (27)
insert into dbo.packages (size) values (52)
insert into dbo.packages (size) values (23)
insert into dbo.packages (size) values (36)
insert into dbo.packages (size) values (29)
insert into dbo.packages (size) values (19)
insert into dbo.packages (size) values (19)
insert into dbo.packages (size) values (39)
insert into dbo.packages (size) values (21)
insert into dbo.packages (size) values (51)
insert into dbo.packages (size) values (20)
insert into dbo.packages (size) values (10)
insert into dbo.packages (size) values (15)
insert into dbo.packages (size) values (43)
insert into dbo.packages (size) values (36)
insert into dbo.packages (size) values (37)
insert into dbo.packages (size) values (50)
insert into dbo.packages (size) values (30)
insert into dbo.packages (size) values (57)
insert into dbo.packages (size) values (29)
insert into dbo.packages (size) values (47)
insert into dbo.packages (size) values (38)
insert into dbo.packages (size) values (32)
insert into dbo.packages (size) values (30)
insert into dbo.packages (size) values (40)
insert into dbo.packages (size) values (35)
insert into dbo.packages (size) values (14)

Before the main code is run the stored procedure reduce_problem is called (see below). This will look for any two packages that will completely fill up a bin. In other words, it does the obvious bin fills, since no alternatives have to be investigated for them.

It will also do this if there is a package that will only allow one more package to fit in the bin, even if the bin will then not be completely full. Again, this is done in this stored procedure, because it is the same for all potential solutions.

It is also important to note, that the column bin_no in table dbo.packages indicates the actual bin (number 1 and higher), whether it has not been processed yet (NULL), or whether it has been processed, but that the bin depends on the potential solution.

Since the assignments that are done in reduce_problem are the same for all potential solutions, it will fill column bin_no with positive numbers.

Another optimization that you see at the end of the stored procedure is the use of the column more_waste. The optimization is, that this column will keep track of the waste in the bins that are no longer part of dbo.tries_B. Table dbo.tries_B lists all active bins for all potential solutions. But it doesn't have to list the bins that are full (or filled up), because the dbo.tries_P and/or dbo.packages table will list which packages are placed in those bins. So the idea is to remove them from dbo.tries_B when they are full or filled up, and record any unused space in those bins in column more_waste. This way, it is still relatively easy to eliminate potential solutions that have too much waste (to be viable).

CREATE PROCEDURE dbo.reduce_problem
(@iteration int
,@bin_size  smallint
) AS
Begin
  Declare @bin_no      smallint
  Declare @rc          int
  Declare @i           int
  Declare @loop        bit
  Declare @package_no  smallint
  Declare @package_no2 smallint
  Declare @size            smallint
  Declare @smallest        smallint
  Declare @second_smallest smallint
  
  -- reduce search space
  -- exact match with 2 packages
  Set @loop=1
  While @loop=1
  Begin
    SELECT TOP 1 @package_no=P1.package_no, @package_no2=P2.package_no
    FROM       dbo.tries_P P1
    CROSS JOIN dbo.tries_P P2
    WHERE (P1.package_no > P2.package_no OR P2.package_no > P1.package_no)
    AND   P1.size         >= P2.size
    AND   P1.size+P2.size =  @bin_size
    AND   P1.bin_no IS NULL
    AND   P2.bin_no IS NULL
    If @@rowcount=0
      Set @loop=0
    Else
    Begin
      SELECT TOP 1 @bin_no=bin_no
      FROM  dbo.tries_B
      WHERE space_left=@bin_size
      If @@rowcount=0
        Set @loop=0
      Else
      Begin
        UPDATE dbo.tries_P
        SET bin_no=@bin_no
        WHERE package_no IN (@package_no,@package_no2)
        
        UPDATE dbo.tries_B
        SET space_left=0
        WHERE bin_no=@bin_no
        
        Set @iteration=@iteration+2
      End
    End
  End
  
  -- reduce search space
  -- fill-up based on 2 packages
  Set @smallest = (SELECT MIN(size) FROM dbo.tries_P WHERE bin_no IS NULL)
  If (SELECT COUNT(*) FROM dbo.tries_P WHERE bin_no IS NULL AND size=@smallest) > 1
    Set @second_smallest = @smallest
  Else
    Set @second_smallest = (SELECT MIN(size) FROM dbo.tries_P WHERE bin_no IS NULL AND size > @smallest)
  
  Set @loop=1
  While @loop=1
  Begin
    SELECT TOP 1 @package_no2=package_no,@size=size
    FROM  dbo.tries_P
    WHERE @smallest + @second_smallest > @bin_size - size
    AND   bin_no IS NULL
    If @@rowcount=0
      Set @loop=0
    Else
    Begin
      SELECT TOP 1 @package_no=package_no
      FROM  dbo.tries_P
      WHERE bin_no IS NULL
      AND   (package_no > @package_no2 OR @package_no2 > package_no)
      AND   @bin_size-@size >= size
      ORDER BY size DESC
      If @@rowcount=0
        Set @loop=0
      Else
      Begin
        SELECT TOP 1 @bin_no=bin_no
        FROM  dbo.tries_B
        WHERE space_left=@bin_size
        If @@rowcount=0
          Set @loop=0
        Else
        Begin
          UPDATE dbo.tries_P
          SET bin_no=@bin_no
          WHERE package_no IN (@package_no,@package_no2)
          
          UPDATE dbo.tries_B
          SET space_left=@bin_size - (
            SELECT SUM(size)
            FROM dbo.tries_P
            WHERE bin_no=@bin_no
          )
          WHERE bin_no=@bin_no
          
          Set @iteration=@iteration+2
        End
      End
    End
  End
  
  UPDATE dbo.packages
  SET bin_no=(
    SELECT bin_no
    FROM dbo.tries_P P
    WHERE P.package_no = dbo.packages.package_no
  )
  
  UPDATE dbo.solutions
  SET more_waste = ISNULL((
    SELECT SUM(space_left)
    FROM dbo.tries_B B WITH (tablock)
    WHERE B.solution = dbo.solutions.solution
    AND   @smallest > B.space_left
  ),0)
  
  -- remove from tries, because they are final and in dbo.packages and dbo.solutions.more_waste
  DELETE FROM dbo.tries_B WHERE @bin_size > space_left
  DELETE FROM dbo.tries_P WHERE bin_no IS NOT NULL
  
  -- remove tries packages except for the next (few)
  DELETE FROM dbo.tries_P
  WHERE bin_no IS NULL
  AND (
    SELECT MAX(size)
    FROM  dbo.tries_P
    WHERE bin_no IS NULL
  ) > size
  Return @iteration
End

The main code relies on four stored procedures that do the real work. The first one is to determine the next package to place. It will fetch the largest remaining package.

It is important to note, that is return the biggest remaining package of the "branch" that is currently handled. The checkpoints table manages this. If there are checkpoints, then the highest checkpoint always indicates the first potential solution of the branch that is actively handled. If there are no checkpoints, the first potential solution is 1.

This stored procedure will also remove the branch from the checkpoints table if the branch has been exhausted and no viable solution has been found.

CREATE PROCEDURE dbo.determine_next_package
(@bin_size smallint
,@debug    bit)
AS
Begin
  -- Big to small
  SET NOCOUNT ON
  Declare @checkpoint int
  SELECT @checkpoint=COALESCE(MAX(solution),1)
  FROM dbo.checkpoints
  
  Declare @package_no smallint
  SELECT TOP 1 @package_no = package_no
  FROM dbo.packages
  WHERE bin_no IS NULL
  ORDER BY size DESC
  
  If @package_no IS NOT NULL
  Begin
    If NOT EXISTS (
      SELECT size
      FROM dbo.tries_P
      WHERE solution=@checkpoint
      AND package_no = @package_no
    )
    Begin
      -- Note: you must run dbo.release_next_packages before calling this SP
      DELETE FROM dbo.solutions   WHERE solution >= @checkpoint
      DELETE FROM dbo.tries_P     WHERE solution >= @checkpoint
      DELETE FROM dbo.tries_B     WHERE solution >= @checkpoint
      
      -- Restore checkpoint, or there is no result
      If @checkpoint>1
      Begin
        UPDATE dbo.packages
        SET bin_no = (
          SELECT bin_no
          FROM dbo.checkpoints AS C
          WHERE C.solution   = @checkpoint
          AND   C.package_no = dbo.packages.package_no
        )
        
        DELETE FROM dbo.checkpoints
        WHERE solution=@checkpoint
        
        SELECT TOP 1 @package_no = package_no
        FROM dbo.packages
        WHERE bin_no IS NULL
        ORDER BY size DESC
      End
    End
  End
  
  If @package_no IS NOT NULL AND @debug = 1
    SELECT 'Biggest Remaining' AS Method, @package_no AS package_no, size FROM dbo.tries_P WHERE solution=@checkpoint AND package_no = @package_no
  
  If @package_no IS NULL AND @debug = 1
    SELECT 'NO PACKAGE FOUND' AS Method
  
  Return @package_no
End

Next is a helper stored procedure that is used by the main assign_package stored procedure, called process_positions. It is a separate stored procedure because the assign_package stored procedure needs this processing for each assignment strategy.

Its purpose is to process the determined package assignment as registered in table dbo.positions in the different working tables.

CREATE PROCEDURE dbo.process_positions
(@package_no      smallint
,@size            smallint
) AS
Begin
    UPDATE dbo.tries_P WITH (tablockx)
    SET bin_no = (
      SELECT bin_no
      FROM dbo.positions T WITH (tablock)
      WHERE T.solution = dbo.tries_P.solution
    )
    WHERE package_no = @package_no
    AND   EXISTS (
      SELECT bin_no
      FROM dbo.positions T WITH (tablock)
      WHERE T.solution = dbo.tries_P.solution
    )
    OPTION (loop join)
   
    UPDATE dbo.tries_B WITH (tablockx)
    SET space_left = space_left - @size
    ,   changed    = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T WITH (tablock)
      WHERE T.solution = dbo.tries_B.solution
      AND   T.bin_no   = dbo.tries_B.bin_no
    )
    OPTION (loop join)
    
    UPDATE dbo.solutions WITH (tablockx)
    SET processed = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T WITH (tablock)
      WHERE T.solution = dbo.solutions.solution
    )
    OPTION (loop join)
End

Next, there is the main part of the code: the stored procedure that will assign a package to a bin, and will create alternative potential solutions when required.

It includes the three strategies of the previous brute force solution: exact matches (which completely fill up a bin), fill up matches if only one more package fits, and regular matches and alternatives, which span new potential solutions.

CREATE PROCEDURE dbo.assign_package
(@package_no            smallint
,@bin_size              smallint
,@number_of_target_bins int
,@debug                 bit
) AS
Begin
  SET NOCOUNT ON
  Declare @checkpoint      int
  Declare @size            smallint
  Declare @smallest        smallint
  Declare @second_smallest smallint
  Declare @rc              int
  Declare @i               int
  Declare @new_id          int
  
  -- Check checkpoints
  SELECT @checkpoint=COALESCE(MAX(solution),1)
  FROM dbo.checkpoints
  
  SELECT @rc=COUNT(*) FROM dbo.solutions WHERE solution >= @checkpoint
  While @rc = 0
  Begin
    -- Restore checkpoint, or there is no result
    UPDATE dbo.packages
    SET bin_no = (
      SELECT bin_no
      FROM dbo.checkpoints AS C
      WHERE C.solution   = @checkpoint
      AND   C.package_no = dbo.packages.package_no
    )
    
    DELETE FROM dbo.checkpoints
    WHERE solution=@checkpoint
    
    SELECT @checkpoint=COALESCE(MAX(solution),1)
    FROM dbo.checkpoints
    
    SELECT @rc=COUNT(*) FROM dbo.solutions WHERE solution >= @checkpoint
    If @checkpoint=1 AND @rc=0
      Set @rc=-1
  End
  
  -- upper limit for the size of a branch
  While @rc > 100000
  Begin
    -- Create new checkpoint
    SELECT @checkpoint=solution
    FROM (
      SELECT solution, ROW_NUMBER() OVER (ORDER BY solution) AS rn
      FROM dbo.solutions WITH (tablock)
      WHERE solution >= @checkpoint
    ) T
    WHERE rn=50001
    
    INSERT INTO dbo.checkpoints (solution,package_no,size,bin_no)
    SELECT @checkpoint,package_no,size,bin_no
    FROM dbo.packages
    
    SELECT @rc=COUNT(*) FROM dbo.solutions WHERE solution >= @checkpoint
  End
  
  Set @size = (SELECT size FROM dbo.packages WHERE package_no=@package_no)
  Set @smallest = (SELECT MIN(size) FROM dbo.packages WHERE bin_no IS NULL)
  If (SELECT COUNT(*) FROM dbo.packages WHERE bin_no IS NULL AND size=@smallest) > 1
    Set @second_smallest = @smallest
  Else
    Set @second_smallest = (SELECT MIN(size) FROM dbo.packages WHERE bin_no IS NULL AND size > @smallest)
  
  SELECT @new_id=MAX(solution) FROM dbo.solutions
  
  UPDATE dbo.solutions  SET processed=0 WHERE processed > 0 AND solution >= @checkpoint
  
  UPDATE dbo.tries_B WITH (tablockx)
  SET changed=0, derived_from=NULL
  WHERE solution >= @checkpoint
  
  -- ** Exact match
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions WITH (tablockx) (solution, more_waste, bins, bin_no)
  SELECT solution, more_waste, bins, (
    SELECT MIN(B.bin_no)
    FROM  dbo.tries_B B WITH (tablock)
    WHERE B.solution=S.solution
    AND   B.space_left = @size
  )
  FROM  dbo.solutions S WITH (tablock)
  WHERE EXISTS (
    SELECT *
    FROM  dbo.tries_B B WITH (tablock)
    WHERE B.solution=S.solution
    AND   B.space_left = @size
  )
  AND solution >= @checkpoint
  OPTION (loop join)
  
  If @@ROWCOUNT > 0
  Begin
    EXEC dbo.process_positions @package_no,@size
    
    If @debug = 1
      SELECT 'Exact Match' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions WITH (tablock)
  End
  
  
  -- ** Fill up
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions WITH (tablockx) (solution, more_waste, bins, bin_no)
  SELECT solution, more_waste, bins, (
    SELECT TOP 1 B.bin_no
    FROM  dbo.tries_B B WITH (tablock)
    WHERE B.solution=S.solution
    AND   B.space_left >= @size
    AND   @smallest + @second_smallest > B.space_left
    AND   @size > B.fill_up
    ORDER BY space_left
  )
  FROM  dbo.solutions S WITH (tablock)
  WHERE S.processed = 0
  AND EXISTS (
    SELECT *
    FROM  dbo.tries_B B WITH (tablock)
    WHERE B.solution=S.solution
    AND   B.space_left >= @size
    AND   @smallest + @second_smallest > B.space_left
    AND   @size > B.fill_up
  )
  AND solution >= @checkpoint
  OPTION (loop join)
  
  If @@ROWCOUNT > 0
  Begin
    EXEC dbo.process_positions @package_no,@size
    
    If @debug = 1
      SELECT 'Fill Up' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions WITH (tablock)
  End
  
  
  -- ** Other / Regular
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions WITH (tablockx) (solution, more_waste, space_left, bin_no)
  SELECT solution, more_waste, space_left, bin_no
  FROM (
    SELECT B.solution, S.more_waste, B.bin_no, B.space_left, ROW_NUMBER() OVER (PARTITION BY B.solution ORDER BY B.space_left) AS rn
    FROM  dbo.tries_B   B
    JOIN  dbo.solutions S
      ON S.solution = B.solution
    WHERE S.processed = 0
    AND   B.space_left >= @size
    AND  (@size > B.fill_up  OR  B.space_left - @size >=  @smallest)
    AND   S.solution >= @checkpoint
  ) T
  WHERE rn = 1
  OPTION (loop join)
  
  If @@rowcount > 0
  Begin
    UPDATE dbo.positions
    SET bins = (
      SELECT bins
      FROM dbo.solutions S WITH (tablock)
      WHERE S.solution = dbo.positions.solution
    )
    OPTION (loop join)
    
    -- create and handle new solutions
    -- the CASE expressions handles suboptimal fill ups (prevents pointless solutions).
    INSERT INTO dbo.solutions WITH (tablockx) (total_waste, more_waste, processed, derived_from, bin_no)
    SELECT 0, MIN(COALESCE(T.more_waste,0)), 2, B.solution, MIN(B.bin_no)
    FROM dbo.positions T WITH (tablock)
    JOIN dbo.tries_B   B WITH (tablock)
      ON B.solution = T.solution
    WHERE (B.space_left > T.space_left OR T.space_left > B.space_left)
    AND   B.space_left >= @size
    AND  (@size > B.fill_up  OR  B.space_left - @size >=  @smallest)
    AND   CASE WHEN @smallest > T.space_left - @size AND @smallest > B.space_left - @size THEN 0 ELSE 1 END = 1
    GROUP BY B.solution, B.space_left
    OPTION (loop join)
    
    If @@ROWCOUNT > 0
    Begin
      UPDATE dbo.solutions
      SET bins = (
        SELECT bins
        FROM dbo.positions T WITH (tablock)
        WHERE T.solution = dbo.solutions.derived_from
      )
      WHERE bins IS NULL
      AND   solution > @new_id
      OPTION (loop join)
      
      If @@rowcount>30000
        UPDATE STATISTICS dbo.solutions
      
      INSERT INTO dbo.tries_P WITH (tablockx) (solution, package_no, size, bin_no)
      SELECT S.solution, P.package_no, P.size, CASE WHEN package_no = @package_no THEN S.bin_no ELSE P.bin_no END
      FROM       dbo.solutions S WITH (tablock)
      INNER JOIN dbo.tries_P   P WITH (tablockx)
        ON P.solution = S.derived_from
      WHERE S.processed = 2
      AND   S.solution >= @checkpoint
      OPTION (loop join)
      
      INSERT INTO dbo.tries_B WITH (tablockx) (solution, bin_no, space_left, fill_up, derived_from, changed)
      SELECT S.solution, B.bin_no, @bin_size - ISNULL(P.space_used,0)
      , CASE WHEN @smallest > B.space_left - @size AND @size > B.fill_up THEN @size ELSE B.fill_up END
      , S.derived_from, CASE WHEN S.bin_no = B.bin_no THEN 1 ELSE 0 END
      FROM            dbo.solutions S WITH (tablock)
      INNER LOOP JOIN dbo.tries_B   B WITH (tablockx)
        ON B.solution = S.derived_from
      LEFT  HASH JOIN (
        SELECT solution, bin_no, SUM(size) AS space_used
        FROM  dbo.tries_P WITH (tablock)
        WHERE solution > @new_id
        GROUP BY solution, bin_no
      ) P
        ON  P.solution = S.solution
        AND P.bin_no   = B.bin_no
      WHERE S.processed = 2
      AND   S.solution > @new_id
      OPTION (force order)
      
      If @debug = 1
        SELECT 'Regular' AS assignment, COUNT(*) AS new_solutions
        FROM dbo.solutions WITH (tablock)
        WHERE processed=2
        AND   solution >= @checkpoint
      
      UPDATE dbo.solutions
      SET   processed=1
      WHERE processed=2
      AND   solution >= @checkpoint
    End
    
    -- handle existing solutions
    EXEC dbo.process_positions @package_no,@size
    
    If @debug = 1
      SELECT 'Regular' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions WITH (tablock)
  End
  
  UPDATE dbo.packages SET bin_no=0 WHERE package_no=@package_no
  
  Set @smallest = (SELECT MIN(size) FROM dbo.packages WHERE bin_no IS NULL)
  
  UPDATE dbo.solutions WITH (tablockx)
  SET total_waste = ISNULL((
    SELECT SUM(space_left)
    FROM dbo.tries_B B WITH (tablock)
    WHERE B.solution = dbo.solutions.solution
    AND   @smallest > B.space_left
  ),0)
  WHERE solution >= @checkpoint
  OPTION (merge join)
End

Next there is the stored procedure that removes potential solutions that cannot complete or are duplicate.

In addition, it contains code to archive a full or filled up bin in the bins columns of dbo.solutions. This storage is much more space efficient than having the rows in dbo.tries_P and dbo.tries_B, and because of that increases performance. It archives the bins in the format >bin<{>package<[,>package<]}. For example, 1{2,3} would indicate that bin 1 consists of package 2 and 3.

Also, this stored procedure will make sure that there is always potential solution 1. When running a checkpoint, it makes sure there is a potential solution for the checkpoint value. So after running this stored procedure, if there is no longer solution 1, then there is no solution!

CREATE PROCEDURE dbo.prune_bins
(@bin_size              smallint
,@number_of_target_bins int
,@debug                 bit
) AS
Begin
  SET NOCOUNT ON
  Declare @rc        int
  Declare @max_waste smallint
  Declare @biggest   smallint
  Declare @bin_no    smallint
  Declare @i         int
  Declare @cnt       int
  Declare @smallest  smallint
  Declare @loop      bit
  Declare @checkpoint int
  
  SELECT @checkpoint=COALESCE(MAX(solution),1)
  FROM dbo.checkpoints
  
  -- eliminate incomplete solutions
  UPDATE dbo.solutions WITH (tablockx)
  SET space_left=(
    SELECT SUM(space_left) AS space_left
    FROM dbo.tries_B B WITH (tablock)
    WHERE B.solution=dbo.solutions.solution
  )
  WHERE solution >= @checkpoint
  OPTION (merge join)
  
  DELETE FROM dbo.solutions
  WHERE space_left+COALESCE(more_waste,0) > (
    SELECT MIN(space_left+COALESCE(more_waste,0))
    FROM dbo.solutions
    WHERE solution >= @checkpoint
  )
  AND solution >= @checkpoint
  OPTION (loop join)
  
  Set @max_waste = (@bin_size * @number_of_target_bins) - (
    SELECT SUM(size)
    FROM dbo.packages
  )
  
  DELETE FROM dbo.solutions WITH (tablockx)
  WHERE total_waste+COALESCE(more_waste,0) > @max_waste
  AND   solution >= @checkpoint
  Set @rc = @@ROWCOUNT
  
  If @rc > 0 AND @debug = 1
    SELECT 'Too much waste' AS Method, @rc AS solutions
  
  -- remove unnecesary bins from tries_B
  Set @smallest = (SELECT MIN(size) FROM dbo.packages WHERE bin_no IS NULL)
  
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions WITH (tablockx) (solution,bin_no,more_waste)
  SELECT solution,bin_no,space_left
  FROM dbo.tries_B WITH (tablock)
  WHERE @smallest > space_left
  AND   solution >= @checkpoint
  If @@rowcount>0
  Begin
    DELETE FROM dbo.tries_B WITH (tablockx)
    WHERE @smallest > space_left
    AND   solution >= @checkpoint
    
    -- the bin
    ;MERGE dbo.solutions AS S -- WITH (tablockx)
    USING dbo.positions AS T WITH (tablock)
      ON  T.solution=S.solution
    WHEN MATCHED THEN UPDATE
      SET more_waste = COALESCE(S.more_waste,0)+T.more_waste
      ,   bins       = COALESCE(S.bins,'')+CAST(T.bin_no AS varchar(10))+'{'
    OPTION (loop join);
    
    -- first package in the bin
    TRUNCATE TABLE dbo.positions2
    
    INSERT INTO dbo.positions2 WITH (tablockx) (solution,package_no)
    SELECT solution,package_no
    FROM (
      SELECT P.solution, P.package_no
      , ROW_NUMBER() OVER (PARTITION BY P.solution ORDER BY P.size DESC,P.package_no) AS rn
      FROM dbo.tries_P   P WITH (tablock)
      JOIN dbo.positions T WITH (tablock)
        ON  T.solution = P.solution
        AND T.bin_no   = P.bin_no
    ) T
    WHERE rn = 1
    OPTION (loop join)
    
    DELETE FROM dbo.tries_P WITH (tablockx)
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions2 T2 WITH (tablock)
      WHERE T2.solution  =dbo.tries_P.solution
      AND   T2.package_no=dbo.tries_P.package_no
    )
    OPTION (loop join)
    
    UPDATE dbo.solutions WITH (tablockx)
    SET bins=bins+(
      SELECT CAST(package_no AS varchar(10))
      FROM dbo.positions2 T2 WITH (tablock)
      WHERE T2.solution=dbo.solutions.solution
    )
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions2 T2 WITH (tablock)
      WHERE T2.solution=dbo.solutions.solution
    )
    OPTION (loop join)
    
    -- all following packages of the bin
    Set @loop=1
    While @loop=1
    Begin
      TRUNCATE TABLE dbo.positions2
      
      INSERT INTO dbo.positions2 WITH (tablockx) (solution,package_no)
      SELECT solution,package_no
      FROM (
        SELECT P.solution, P.package_no
        , ROW_NUMBER() OVER (PARTITION BY P.solution ORDER BY P.size DESC,P.package_no) AS rn
        FROM dbo.tries_P   P WITH (tablock)
        JOIN dbo.positions T WITH (tablock)
          ON  T.solution = P.solution
          AND T.bin_no   = P.bin_no
      ) T
      WHERE rn = 1
      OPTION (loop join)
      
      If @@rowcount=0
        Set @loop=0
      Else
      Begin
        DELETE FROM dbo.tries_P WITH (tablockx)
        WHERE EXISTS (
          SELECT *
          FROM dbo.positions2 T2 WITH (tablock)
          WHERE T2.solution  =dbo.tries_P.solution
          AND   T2.package_no=dbo.tries_P.package_no
        )
        OPTION (loop join)
        
        UPDATE dbo.solutions WITH (tablockx)
        SET bins=bins+','+(
          SELECT CAST(package_no AS varchar(10))
          FROM dbo.positions2 T2 WITH (tablock)
          WHERE T2.solution=dbo.solutions.solution
        )
        WHERE EXISTS (
          SELECT *
          FROM dbo.positions2 T2 WITH (tablock)
          WHERE T2.solution=dbo.solutions.solution
        )
        OPTION (loop join)
      End
    End
    
    -- close the bin
    ;MERGE dbo.solutions AS S -- WITH (tablockx)
    USING dbo.positions AS T WITH (tablock)
      ON  T.solution=S.solution
    WHEN MATCHED THEN UPDATE
      SET bins = S.bins+'}'
    OPTION (loop join);
    
  End
  
  TRUNCATE TABLE dbo.duplicates
  
  -- by definition, if the remaining space and space distribution / number of elements is identical,
  -- then for this purpose the parts removed from tries_B are equivalent too
  INSERT INTO dbo.duplicates WITH (tablockx) (solution, packages)
  SELECT T1.solution, (
    SELECT cast(',' AS VARCHAR(900)) + CASE WHEN @bin_size > T2.space_left THEN CAST(T2.space_left AS varchar(10)) ELSE 'E' END
    FROM dbo.tries_B AS T2 WITH (tablock)
    WHERE T2.solution = T1.solution
    ORDER BY T2.space_left
    FOR XML PATH('')  
  ) AS packages
  FROM dbo.solutions AS T1 WITH (tablock)
  WHERE solution >= @checkpoint
  OPTION (loop join)
  
  DELETE FROM dbo.duplicates WITH (tablockx)
  WHERE solution = (SELECT MIN(solution) FROM dbo.duplicates T1 WITH (tablockx) WHERE T1.packages=dbo.duplicates.packages)
  
  DELETE FROM dbo.solutions WITH (tablockx)
  WHERE EXISTS (
    SELECT *
    FROM dbo.duplicates T1 WITH (tablock)
    WHERE T1.solution = dbo.solutions.solution
  )
  OPTION (loop join)
  Set @rc=@@ROWCOUNT
  
  If @rc > 0 AND @debug = 1
    SELECT 'Duplicate solutions' AS Method, @rc AS solutions
  
  -- cleanup...
  DELETE FROM dbo.tries_B WITH (tablockx)
  WHERE NOT EXISTS (
    SELECT *
    FROM dbo.solutions S WITH (tablock)
    WHERE S.solution = dbo.tries_B.solution
  )
  AND solution >= @checkpoint
  OPTION (hash join)
  
  DELETE FROM dbo.tries_P WITH (tablockx)
  WHERE NOT EXISTS (
    SELECT *
    FROM dbo.solutions S WITH (tablock)
    WHERE S.solution = dbo.tries_P.solution
  )
  AND solution >= @checkpoint
  OPTION (hash join)
  
  IF NOT EXISTS (
    SELECT *
    FROM dbo.solutions
    WHERE solution=@checkpoint
  )
  Begin
    -- rebase a solution
    Declare @old int
    Set @old = (SELECT TOP 1 solution FROM dbo.solutions WHERE solution >= @checkpoint)
    
    If @debug = 1
      SELECT 'Re-establishing solution 1' AS Method, @old AS old_solution
    
    SET IDENTITY_INSERT dbo.solutions ON
    
    INSERT INTO dbo.solutions (solution, total_waste, more_waste, processed, derived_from, bin_no, space_left, bins)
    SELECT @checkpoint, total_waste, more_waste, processed, derived_from, bin_no, space_left, bins
    FROM dbo.solutions WITH (tablockx)
    WHERE solution=@old
    
    SET IDENTITY_INSERT dbo.solutions OFF
    
    DELETE FROM dbo.solutions
    WHERE solution=@old
    
    UPDATE dbo.tries_B
    SET solution=@checkpoint
    WHERE solution=@old
    
    UPDATE dbo.tries_P
    SET solution=@checkpoint
    WHERE solution=@old
  End
End

Then there is the stored procedure that add the next portion of packages to dbo.tries_P. They are not all added immediately after inception of a new potential solution to save space. Since most potential solutions are not viable and will be deleted, it saves space and time to not add them in the first place.

This stored procedures adds the next package(s) just in time

CREATE PROCEDURE dbo.release_next_packages AS
Begin
  -- add new packages to tries_P when needed
  Declare @size smallint
  Declare @i  int
  Declare @rc int
  Declare @checkpoint      int
  SELECT @checkpoint=COALESCE(MAX(solution),1)
  FROM dbo.checkpoints
  
  If NOT EXISTS (
    SELECT *
    FROM  dbo.tries_P
    WHERE solution=@checkpoint
    AND   bin_no IS NULL
  )
  Begin
    Set @size=NULL
    
    SELECT @size=MIN(size)
    FROM  dbo.tries_P
    WHERE solution=@checkpoint
    AND   bin_no IS NOT NULL
    
    SELECT @size=MAX(size)
    FROM  dbo.packages
    WHERE bin_no IS NULL
    AND   @size > size
    
    INSERT INTO dbo.tries_P WITH (tablockx) (solution, package_no, bin_no, size)
    SELECT S.solution, P.package_no, NULL, P.size
    FROM       dbo.solutions S WITH (tablock)
    CROSS JOIN dbo.packages  P WITH (tablock)
    WHERE P.size = @size
    AND   P.bin_no IS NULL
    AND   S.solution >= @checkpoint
    OPTION (maxdop 1)
  End
End

And finally the main executable batch. It does the final preparation and loops through all the packages, placing them one at a time, and reporting progress while running. When found, the solution is printed.

When it is done, and there is a solution, it unpacks the archives bins. In the end, the final solution is captured in the dbo.packages table.

Make sure you set the number of target bins appropriately!

TRUNCATE TABLE dbo.positions
TRUNCATE TABLE dbo.solutions
TRUNCATE TABLE dbo.checkpoints
TRUNCATE TABLE dbo.tries_B
TRUNCATE TABLE dbo.tries_P

UPDATE dbo.packages
SET bin_no = NULL

Declare @solution int
INSERT INTO dbo.solutions (processed,total_waste,more_waste) VALUES (0,0,0)
set @solution=@@IDENTITY

INSERT INTO dbo.tries_P (solution, package_no, bin_no, size)
SELECT @solution, package_no, NULL, size
FROM dbo.packages

Declare @number_of_target_bins int
Set @number_of_target_bins = 18
Declare @bin_size   smallint
Set @bin_size = 100

INSERT INTO dbo.tries_B (solution, bin_no, space_left, fill_up, changed)
SELECT @solution, n, @bin_size, 0, 0
FROM dbo.numbers
WHERE n BETWEEN 1 AND @number_of_target_bins

Declare @dt    datetime
Declare @dt_np datetime
Declare @dt_ap datetime
Declare @dt_pb datetime
Declare @iteration   int
Declare @package_no  smallint
Declare @bin_no      smallint
Declare @size        smallint
Declare @debug bit
Set @debug=0

Set @iteration = 1

EXEC @iteration = dbo.reduce_problem @iteration, @bin_size

While EXISTS (SELECT * FROM dbo.solutions)
  AND EXISTS (SELECT * FROM dbo.tries_P WHERE bin_no IS NULL AND solution=(SELECT COALESCE(MAX(solution),1) FROM dbo.checkpoints))
Begin
  Set @dt=CURRENT_TIMESTAMP
  EXEC @package_no = dbo.determine_next_package @bin_size, @debug
  Set @dt_np=CURRENT_TIMESTAMP
  EXEC dbo.assign_package @package_no, @bin_size, @number_of_target_bins, @debug
  Set @dt_ap=CURRENT_TIMESTAMP
  EXEC dbo.prune_bins @bin_size, @number_of_target_bins, @debug
  EXEC dbo.release_next_packages
  Set @dt_pb=CURRENT_TIMESTAMP
  
  SELECT @iteration AS iteration
  ,      @package_no AS package_no
  ,      COUNT(*) AS solutions
  ,      DATEDIFF(ms,@dt, @dt_pb) AS total_performance
  ,      DATEDIFF(ms,@dt, @dt_np) AS perf_np
  ,      DATEDIFF(ms,@dt_np, @dt_ap) AS perf_ap
  ,      DATEDIFF(ms,@dt_ap, @dt_pb) AS perf_pb
  FROM dbo.solutions
  
  Set @iteration=@iteration+1
End

If EXISTS (SELECT * FROM dbo.solutions)
  AND NOT EXISTS (SELECT * FROM dbo.tries_P WHERE bin_no IS NULL AND solution=(SELECT COALESCE(MAX(solution),1) FROM dbo.checkpoints))
Begin
  -- rebase a solution
  Declare @old int
  Set @old = (SELECT COALESCE(MAX(solution),1) FROM dbo.checkpoints)
  If @old>1
  Begin
    If @debug = 1
      SELECT 'Re-establishing solution 1' AS Method, @old AS old_solution
    
    DELETE FROM dbo.solutions WHERE solution=1
    
    SET IDENTITY_INSERT dbo.solutions ON
    
    INSERT INTO dbo.solutions (solution, total_waste, more_waste, processed, derived_from, bin_no, space_left, bins)
    SELECT 1, total_waste, more_waste, processed, derived_from, bin_no, space_left, bins
    FROM dbo.solutions WITH (tablockx)
    WHERE solution=@old
    
    SET IDENTITY_INSERT dbo.solutions OFF
    
    DELETE FROM dbo.solutions
    WHERE solution=@old
    
    DELETE FROM dbo.tries_B WHERE solution=1
    
    UPDATE dbo.tries_B
    SET solution=1
    WHERE solution=@old
    
    DELETE FROM dbo.tries_P WHERE solution=1
    
    UPDATE dbo.tries_P
    SET solution=1
    WHERE solution=@old
  End
End

-- commit solution to packages
UPDATE dbo.packages
SET bin_no = (
  SELECT bin_no
  FROM dbo.tries_P
  WHERE solution=1
  AND   package_no = dbo.packages.package_no
)
WHERE EXISTS (
  SELECT bin_no
  FROM dbo.tries_P
  WHERE solution=1
  AND   package_no = dbo.packages.package_no
)

-- Expand packed bins
Declare @bins varchar(4000)
Declare @at   int
Declare @at2  int
Set @bins=(SELECT COALESCE(bins,'') FROM dbo.solutions WHERE solution=1)
While @bins > ''
Begin
  Set @at=CHARINDEX('{',@bins)
  Set @bin_no=SUBSTRING(@bins,1,@at-1)
  Set @bins=SUBSTRING(@bins,@at+1,4000)
  
  Set @at=CHARINDEX('}',@bins)
  Set @at2=CHARINDEX(',',@bins)
  While @at2>0 AND @at>@at2
  Begin
    UPDATE dbo.packages
    SET   bin_no = @bin_no
    WHERE package_no=SUBSTRING(@bins,1,@at2-1)
    
    Set @bins=SUBSTRING(@bins,@at2+1,4000)
    Set @at=CHARINDEX('}',@bins)
    Set @at2=CHARINDEX(',',@bins)
  End
  
  UPDATE dbo.packages
  SET   bin_no = @bin_no
  WHERE package_no=SUBSTRING(@bins,1,@at-1)
  
  Set @bins=SUBSTRING(@bins,@at+1,4000)
End

SELECT * FROM dbo.packages ORDER BY bin_no, size DESC, package_no
-- doublecheck: select bin_no,sum(size) from dbo.packages group by bin_no order by 1


Part 7 - Solution 7


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