Bin Packing - part 7

package_no  size
----------- ------
1           36
2           39
3           43
4           53
5           32
6            7
7           23
8           41
9           55
10          29
11          14
12          44
13          44
14          22
15          32
16          52
17          38
18          16
19          31
20          36

-- set up base tables
CREATE TABLE dbo.solutions
(solution     bigint   IDENTITY PRIMARY KEY CLUSTERED
,processed    tinyint  NOT NULL
,total_waste  smallint NOT NULL
,derived_from bigint       NULL
,bin_no       int          NULL
)

CREATE TABLE dbo.positions
(solution    bigint   NOT NULL
,bin_no      int      NOT NULL
,space_left  smallint     NULL
,CONSTRAINT PK_positions PRIMARY KEY CLUSTERED (solution, bin_no)
)

CREATE TABLE dbo.tries_P
(solution       bigint   NOT NULL
,package_no     int      NOT NULL
,size           smallint NOT NULL
,bin_no         int          NULL
,CONSTRAINT PK_tries_P PRIMARY KEY CLUSTERED(solution,package_no)
)
CREATE INDEX IX_tries_P_package_no ON dbo.tries_P (package_no)

CREATE TABLE dbo.tries_B
(solution     bigint   NOT NULL
,bin_no       int      NOT NULL
,space_left   smallint NOT NULL
,fill_up      int          NULL
,derived_from bigint       NULL
,changed      bit          NULL
,CONSTRAINT PK_tries_B PRIMARY KEY CLUSTERED (solution,bin_no)
)
CREATE INDEX IX_tries_B_space_left ON dbo.tries_B (space_left, solution) INCLUDE (bin_no, fill_up)


-- 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

-- scenario setup
CREATE TABLE dbo.packages
(package_no int      IDENTITY PRIMARY KEY
,size       smallint NOT NULL
,bin_no     int          NULL
)
CREATE INDEX IX_packages_binno_size ON dbo.packages(bin_no,size)

INSERT INTO dbo.packages(size) VALUES (36)
INSERT INTO dbo.packages(size) VALUES (39)
INSERT INTO dbo.packages(size) VALUES (43)
INSERT INTO dbo.packages(size) VALUES (53)
INSERT INTO dbo.packages(size) VALUES (32)
INSERT INTO dbo.packages(size) VALUES (7)
INSERT INTO dbo.packages(size) VALUES (23)
INSERT INTO dbo.packages(size) VALUES (41)
INSERT INTO dbo.packages(size) VALUES (55)
INSERT INTO dbo.packages(size) VALUES (29)
INSERT INTO dbo.packages(size) VALUES (14)
INSERT INTO dbo.packages(size) VALUES (44)
INSERT INTO dbo.packages(size) VALUES (44)
INSERT INTO dbo.packages(size) VALUES (22)
INSERT INTO dbo.packages(size) VALUES (32)
INSERT INTO dbo.packages(size) VALUES (52)
INSERT INTO dbo.packages(size) VALUES (38)
INSERT INTO dbo.packages(size) VALUES (16)
INSERT INTO dbo.packages(size) VALUES (31)
INSERT INTO dbo.packages(size) VALUES (36)

CREATE PROCEDURE dbo.determine_next_package
(@bin_size smallint
,@debug    bit)
AS
Begin
  -- Big to small
  SET NOCOUNT ON
  Declare @package_no int
  SELECT TOP 1 @package_no = package_no
  FROM dbo.tries_P
  WHERE solution=1
  AND   bin_no IS NULL
  ORDER BY size DESC
  
  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=1 AND package_no = @package_no
  
  If @package_no IS NULL AND @debug = 1
    SELECT 'NO PACKAGE FOUND' AS Method
  
  Return @package_no
End

CREATE PROCEDURE dbo.assign_package
(@package_no            int
,@bin_size              smallint
,@number_of_target_bins int
,@debug                 bit
) AS
Begin
  SET NOCOUNT ON
  Declare @size            smallint
  Declare @smallest        smallint
  Declare @second_smallest smallint
  
  Set @size = (SELECT size FROM dbo.tries_P WHERE solution=1 AND package_no=@package_no)
  Set @smallest = (SELECT MIN(size) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL)
  If (SELECT COUNT(*) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL AND size=@smallest) > 1
    Set @second_smallest = @smallest
  Else
    Set @second_smallest = (SELECT MIN(size) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL AND size > @smallest)
  
  UPDATE dbo.solutions  SET processed=0 WHERE processed > 0
  UPDATE dbo.tries_B    SET changed=0, derived_from=NULL
  
  -- ** Exact match
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions (solution, bin_no)
  SELECT solution, MIN(bin_no)
  FROM  dbo.tries_B B
  WHERE B.space_left = @size
  GROUP BY solution
  
  If @@ROWCOUNT > 0
  Begin
    UPDATE dbo.tries_P
    SET bin_no = (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    WHERE package_no = @package_no
    AND   EXISTS (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
   
    UPDATE dbo.tries_B
    SET space_left = space_left - @size
    ,   changed    = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_B.solution
      AND   T.bin_no   = dbo.tries_B.bin_no
    )
    
    UPDATE dbo.solutions
    SET processed = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.solutions.solution
    )
    
    If @debug = 1
      SELECT 'Exact Match' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions
  End
  
  
  -- ** Real Fill Up
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions (solution, bin_no)
  SELECT solution, bin_no
  FROM (
    SELECT B.solution, B.bin_no, 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   B.space_left <  @second_smallest
  ) T
  WHERE rn = 1
  
  If @@ROWCOUNT > 0
  Begin
    -- handle existing solutions
    UPDATE dbo.tries_P
    SET bin_no = (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    WHERE package_no = @package_no
    AND   EXISTS (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    
    UPDATE dbo.tries_B
    SET space_left = space_left - @size
    ,   changed    = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_B.solution
      AND   T.bin_no   = dbo.tries_B.bin_no
    )
    
    UPDATE dbo.solutions
    SET processed = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.solutions.solution
    )
    
    If @debug = 1
      SELECT 'Real Fill Up' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions
  End
  
  
  -- ** Fill up
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions (solution, bin_no)
  SELECT solution, bin_no
  FROM (
    SELECT B.solution, B.bin_no, 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   B.space_left <  @smallest + @second_smallest
    AND   B.fill_up    <  @size
  ) T
  WHERE rn = 1
  
  If @@ROWCOUNT > 0
  Begin
    -- create and handle new solutions
    INSERT INTO dbo.solutions (total_waste, processed, derived_from, bin_no)
    SELECT 0, 2, B.solution, MIN(B.bin_no)
    FROM dbo.positions T
    JOIN dbo.tries_B   B
      ON B.solution = T.solution
    WHERE B.space_left >= @smallest + @second_smallest
    AND   B.space_left >= @size
    AND   B.fill_up    <  @size
    GROUP BY B.solution, B.space_left
    
    INSERT INTO dbo.tries_P (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
    JOIN dbo.tries_P   P
      ON P.solution = S.derived_from
    WHERE S.processed = 2
    
    INSERT INTO dbo.tries_B (solution, bin_no, space_left, fill_up, derived_from, changed)
    SELECT S.solution, B.bin_no, @bin_size - ISNULL((
      SELECT SUM(P.size)
      FROM  dbo.tries_P P
      WHERE P.solution = S.solution
      AND   P.bin_no   = B.bin_no
    ),0), CASE WHEN B.space_left - @size < @smallest 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
    JOIN dbo.tries_B   B
      ON B.solution = S.derived_from
    WHERE S.processed = 2
    
    If @debug = 1
    Begin
      Declare @rc int
      Set @rc=(SELECT COUNT(*) FROM dbo.solutions WHERE processed=2)
      If @rc>0
        SELECT 'Fill Up' AS assignment, @rc AS new_solutions
    End
    
    UPDATE dbo.solutions
    SET   processed=1
    WHERE processed=2
    
    -- handle existing solutions
    UPDATE dbo.tries_P
    SET bin_no = (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    WHERE package_no = @package_no
    AND   EXISTS (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    
    UPDATE dbo.tries_B
    SET space_left = space_left - @size
    ,   changed    = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_B.solution
      AND   T.bin_no   = dbo.tries_B.bin_no
    )
    
    UPDATE dbo.solutions
    SET processed = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.solutions.solution
    )
    
    If @debug = 1
      SELECT 'Fill Up' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions
  End
  
  
  -- ** Other / Regular
  TRUNCATE TABLE dbo.positions
  
  INSERT INTO dbo.positions (solution, bin_no, space_left)
  SELECT solution, bin_no, space_left
  FROM (
    SELECT B.solution, 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  (B.fill_up    <  @size  OR  B.space_left - @size >=  @smallest)
  ) T
  WHERE rn = 1
  
  If @@rowcount > 0
  Begin
    -- create and handle new solutions
    -- the CASE expressions handles suboptimal fill ups (prevents pointless solutions).
    INSERT INTO dbo.solutions (total_waste, processed, derived_from, bin_no)
    SELECT 0, 2, B.solution, MIN(B.bin_no)
    FROM dbo.positions T
    JOIN dbo.tries_B   B
      ON B.solution = T.solution
    WHERE B.space_left <> T.space_left
    AND   B.space_left >= @size
    AND  (B.fill_up    <  @size  OR  B.space_left - @size >=  @smallest)
    AND   CASE WHEN T.space_left - @size < @smallest AND B.space_left - @size < @smallest THEN 0 ELSE 1 END = 1
    GROUP BY B.solution, B.space_left
    
    If @@ROWCOUNT > 0
    Begin
      -- *** can take a long time, longer than the next
      -- ** HASH JOIN outperforms LOOP JOIN here
      INSERT INTO dbo.tries_P (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
      INNER HASH JOIN dbo.tries_P   P
        ON P.solution = S.derived_from
      WHERE S.processed = 2
      OPTION (force order)
      
      -- *** can take quite some time...
      -- ** HASH JOIN outperforms LOOP JOIN here
      INSERT INTO dbo.tries_B (solution, bin_no, space_left, fill_up, derived_from, changed)
      SELECT S.solution, B.bin_no, @bin_size - ISNULL((
        SELECT SUM(P.size)
        FROM  dbo.tries_P P
        WHERE P.solution = S.solution
        AND   P.bin_no   = B.bin_no
      ),0), CASE WHEN B.space_left - @size < @smallest 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
      INNER HASH JOIN dbo.tries_B   B
        ON B.solution = S.derived_from
      WHERE S.processed = 2
      OPTION (force order)
      
      If @debug = 1
        SELECT 'Regular' AS assignment, COUNT(*) AS new_solutions
        FROM dbo.solutions
        WHERE processed=2
      
      UPDATE dbo.solutions
      SET   processed=1
      WHERE processed=2
    End
    
    -- handle existing solutions
    UPDATE dbo.tries_P
    SET bin_no = (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    WHERE package_no = @package_no
    AND   EXISTS (
      SELECT bin_no
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_P.solution
    )
    
    UPDATE dbo.tries_B
    SET space_left = space_left - @size
    ,   changed    = 1
    WHERE EXISTS (
      SELECT *
      FROM dbo.positions T
      WHERE T.solution = dbo.tries_B.solution
      AND   T.bin_no   = dbo.tries_B.bin_no
    )
    
    If @debug = 1
      SELECT 'Regular' AS assignment, COUNT(*) AS solutions
      FROM dbo.positions
  End
  
  Set @smallest = (SELECT MIN(size) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL)
  
  UPDATE dbo.solutions
  SET total_waste = ISNULL((
    SELECT SUM(space_left)
    FROM dbo.tries_B B
    WHERE B.solution = dbo.solutions.solution
    AND   B.space_left < @smallest
  ),0)
End

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 int
  Declare @size      int
  Declare @biggest   int
  Declare @bin_no    int
  
  -- eliminate incomplete solutions
  SELECT @size=MIN(space_left)
  FROM (
    SELECT SUM(space_left) AS space_left
    FROM dbo.tries_B
    GROUP BY solution
  ) Regular
  
  DELETE FROM dbo.solutions
  WHERE EXISTS (
    SELECT SUM(space_left) 
    FROM dbo.tries_B B
    WHERE B.solution = dbo.solutions.solution
    HAVING SUM(space_left) > @size
  )
  
  -- delete solution with too much waste
  Set @max_waste = (@bin_size * @number_of_target_bins) - (
    SELECT SUM(size)
    FROM dbo.tries_P
    WHERE solution=1
  )
  
  DELETE FROM dbo.solutions
  WHERE total_waste > @max_waste
  Set @rc = @@ROWCOUNT
  
  If @rc > 0 AND @debug = 1
    SELECT 'Too much waste' AS Method, @rc AS solutions
  
  -- quick cross check if there is sufficient free space for large amount of big packages
  Set @rc = 0
  Set @biggest = (SELECT MAX(size) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL)
  Set @size = @biggest
  
  While @size > @biggest / 2
  Begin
    Set @rc = (SELECT COUNT(*) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL and size >= @size)
    
    DELETE FROM dbo.solutions
    WHERE (
      SELECT SUM(space_left / @size) 
      FROM dbo.tries_B B
      WHERE B.solution = dbo.solutions.solution
    ) < @rc
    Set @rc=@@ROWCOUNT
    
    If @rc > 0 AND @debug = 1
      SELECT 'Not all big packages fit' AS Method, @rc AS solutions
    
    Set @size = (SELECT MAX(size) FROM dbo.tries_P WHERE solution=1 AND bin_no IS NULL AND size < @size)
  End
  
  -- solutions may have been removed. Clean up, so it is consistent again
  DELETE FROM dbo.tries_B
  WHERE NOT EXISTS (
    SELECT *
    FROM dbo.solutions S
    WHERE S.solution = dbo.tries_B.solution
  )
  
  DELETE FROM dbo.tries_P
  WHERE NOT EXISTS (
    SELECT *
    FROM dbo.solutions S
    WHERE S.solution = dbo.tries_P.solution
  )
  
  IF NOT EXISTS (
    SELECT *
    FROM dbo.solutions
    WHERE solution=1
  )
  Begin
    -- solution 1 was removed. Rebase a solution
    Declare @old int
    Set @old = (SELECT TOP 1 solution FROM dbo.solutions)
    
    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, processed, derived_from, bin_no)
    SELECT 1, total_waste, processed, derived_from, bin_no
    FROM dbo.solutions
    WHERE solution=@old
    
    SET IDENTITY_INSERT dbo.solutions OFF
    
    DELETE FROM dbo.solutions
    WHERE solution=@old
    
    UPDATE dbo.tries_B
    SET solution=1
    WHERE solution=@old
    
    UPDATE dbo.tries_P
    SET solution=1
    WHERE solution=@old
  End
 End

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

Declare @solution bigint
INSERT INTO dbo.solutions (processed,total_waste) VALUES (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 = 7
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 int
Declare @debug bit
Set @debug=0

Set @iteration = 1
While EXISTS (SELECT * FROM dbo.solutions)
  AND EXISTS (SELECT * FROM dbo.tries_P WHERE bin_no IS NULL)
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
  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

SELECT * FROM dbo.tries_P WHERE solution=1 ORDER BY bin_no, size DESC, package_no