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
-- 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)
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
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
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
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
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
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
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
Back to SQL Server main menu. Mail your comments to gertjans@xs4all.nl.