Hi all,
I have a type of simple bin-packing problem that I am having trouble writing a recursive CTE for. I'm using 11g.
The data looks like this:
create table test_packing
(id number(3),
startt number(3),
endt number(3));
insert into test_packing values (1,1,4);
insert into test_packing values (2,2,5);
insert into test_packing values (3,4,6);
insert into test_packing values (4,5,6);
insert into test_packing values (5,6,9);
insert into test_packing values (6,7,11);
insert into test_packing values (7,10,12);
insert into test_packing values (8,2,8);
insert into test_packing values (9,1,6);
insert into test_packing values (10,8,12);
insert into test_packing values (11,7,11);
insert into test_packing values (12,11,12);
insert into test_packing values (13,1,12);
You should think of the startt and endt values as hours of the day, maximum 12 hours. I want to pack each "bin" with as many non-overlapping rows as possible. Not too worried about getting the optimal solution.
So, for example, if you start with the first row, which ends at 4, you can then add row 3, which starts at 4 and ends at 6, then row 5 which starts at 6 and ends at 9, followed by row 7, which starts at 10 and ends at 12.
That's the end of the day, so then you have to start a new bin, and you'd start your new day with either row 9 or row 13, which both start at 1.
One possible end result (the bin numbers could be different) is:
| ID | STARTT | ENDT | BIN_NUM |
| 1 | 1 | 4 | 1 |
| 3 | 4 | 6 | 1 |
| 5 | 6 | 9 | 1 |
| 7 | 10 | 12 | 1 |
| 13 | 1 | 12 | 2 |
| 9 | 1 | 6 | 3 |
| 11 | 7 | 11 | 3 |
| 12 | 11 | 12 | 3 |
| 2 | 2 | 5 | 4 |
| 4 | 5 | 6 | 4 |
| 6 | 7 | 11 | 4 |
| 8 | 2 | 8 | 5 |
| 10 | 8 | 12 | 5 |
I have an algorithm which works for finding the next row to add to the bin (or to start a new bin), but I'm having trouble turning it into a recursive CTE.
Basically, the algorithm is:
Get the end time for the current bin being worked on and the number of the current bin.
Order the unpacked items by start-time, with a penalty for those that start too early to fit in the current bin (start time is less than current bin end)
Put the first item from the list into the current bin, or start a new bin if necessary.
Go back to the beginning.
The algorithm is:
with cstate as -- starting state
(select id,startt,endt, case when id in (1,3,5,7) then 1 when id = 13 then 2 when id in (9,11,12) then 3 when id in (2,4,6) then 4 when id in (8,10) then 5 end bin_num
from test_packing
)
, current_end as -- max end in last bin and current bin #
(select max(endt) keep (dense_rank last order by bin_num,endt) cend,max(bin_num) current_bin
from cstate
where bin_num is not null
)
, current_ranking as -- get ordering of current unallocated set (and union the allocated ones)
(select id,startt,endt
,case when bin_num is null then
case when s.startt < nvl(e.cend,0) then 12 + s.startt else s.startt end
end compval,null bin_num
from cstate s
cross join current_end e
where bin_num is null
UNION ALL
select id,startt,endt,99,bin_num
from cstate
where bin_num is not null
)
-- new set
select id,startt,endt,case when bin_num is not null then bin_num else case when rn = 1 then nvl(current_bin,0)+new_bin end end bin_num
from
(select id,startt,endt,case when c.compval > 12 then 1 else 0 end new_bin
,row_number() over (order by c.compval) rn
,e.current_bin
,bin_num
from current_ranking c
cross join current_end e
)
order by id ;
I can set any starting point modifying the case statement in the first row, and have the algorithm put the next row in the bin. The bin ordering of the first three rows (all start at hour one) and the last two (both start at hour two), is arbitrary.
One version of the CTE I tried that does not work (says "ORA-32042: recursive WITH clause must reference itself directly in one of the UNION ALL branches") is:
with bin_pack(id,startt,endt,bin_num) as
(select id,startt,endt,NULL bin_num
from test_packing
UNION ALL
(select id,startt,endt,case when bin_num is not null then bin_num else case when rn = 1 then current_bin+new_bin end end bin_num
from
(select id,startt,endt,case when c.compval > 12 then 1 else 0 end new_bin
,row_number() over (order by c.compval) rn
,e.current_bin
, bin_num
from
(select id,startt,endt
,case when bin_num is null then
case when s.startt < nvl(e.cend,0) then 12 + s.startt else s.startt end
end compval
, bin_num
from
(select id,startt,endt
,case when bin_num is null then
case when s.startt < nvl(e.cend,0) then 12 + s.startt else s.startt end
end compval,null bin_num
from bin_pack s
cross join
(select max(endt) keep (dense_rank last order by bin_num,endt) cend,max(bin_num) current_bin
from bin_pack
where bin_num is not null
) e
where bin_num is null
UNION ALL
select id,startt,endt,99,bin_num
from bin_pack
where bin_num is not null
) s
cross join
(select max(endt) keep (dense_rank last order by bin_num,endt) cend,max(bin_num) current_bin
from bin_pack
where bin_num is not null
) e
) c
cross join
(select max(endt) keep (dense_rank last order by bin_num,endt) cend,max(bin_num) current_bin
from bin_pack
where bin_num is not null
) e
)
)
)
select *
from bin_pack;
A previous version had the UNION ALL of the already-packed items at the bottom (the new set portion of the original code), but that got a "can only have one UNION ALL" error.
Any way of rewriting it so that it does what it is supposed to?
Thanks.